Java中int转Bigint计算结果不一致问题排查

看起来你是把int版的快速幂求模转换成BigInteger时遇到了结果不匹配的问题，我帮你梳理下最容易出错的几个点，你可以逐一排查：

1. 初始值是否正确 #

原int版的result初始值肯定是1（快速幂的累积初始值必须是1，因为任何数的0次方为1）。如果转换时你不小心把result初始成了BigInteger.ZERO，那整个计算结果都会是0，必然和原代码不一致。

检查你的BigInteger代码开头，是不是写了：

BigInteger result = BigInteger.ONE;

2. 运算方法调用是否符合BigInteger规则 #

BigInteger不能用*、%、/这些基本运算符，必须用类自带的方法，这是最容易踩的坑：

• 原代码的result = (result * base) % modulus; → 正确转换应该是：

  result = result.multiply(base).mod(modulus);
  

• 原代码的exponent = exponent / 2; → 正确转换应该是：

  exponent = exponent.divide(BigInteger.TWO);
  

• 原代码的base = (base * base) % modulus; → 正确转换应该是：

  base = base.multiply(base).mod(modulus);
  

如果这里你误用了运算符（比如还写了%），或者方法顺序错了，都可能导致结果偏差。

3. 所有变量是否都正确转为BigInteger #

如果原代码里的base、exponent、modulus有一个没转成BigInteger，比如modulus还是int类型，当它的值超过int范围时，会因为int溢出变成负数，而BigInteger是精确存储的，这时候模运算的结果肯定不一样。

比如原int的modulus如果是2147483648，int会溢出成-2147483648，而BigInteger的2147483648是正确值，两者的模计算结果完全不同。

确保所有变量都转成BigInteger：

BigInteger base = BigInteger.valueOf(originalBaseInt);
BigInteger exponent = BigInteger.valueOf(originalExponentInt);
BigInteger modulus = BigInteger.valueOf(originalModulusInt);

4. 原int代码是否存在溢出导致的“假结果” #

这里要注意：int的范围是-2^31到2^31-1，当result * base或base * base超过这个范围时，会发生整数溢出，得到的是溢出后的错误值；而BigInteger是精确计算，不会溢出，所以结果会和原int版本不一样。

比如原int代码计算(1000000 * 1000000) % 2147483647，int乘法溢出后得到-727379968，取模结果是1420103679；但BigInteger精确计算的结果是1705032704——这时候差异是因为原int代码本身就错了，BigInteger的结果才是正确的。

排查小技巧 #

先用一组不会溢出的小测试值验证，比如base=2、exponent=3、modulus=5：

• 原int代码结果应该是3（2^3%5=3）
• 如果BigInteger代码结果也是3，说明转换逻辑没问题，差异只是原int代码的溢出导致的；
• 如果小值结果也不一致，那肯定是初始值或方法调用的错误，再逐行核对代码。

最后给你一个标准的BigInteger版快速幂求模代码，你可以对比参考：

public static BigInteger fastModPow(BigInteger base, BigInteger exponent, BigInteger modulus) {
    BigInteger result = BigInteger.ONE;
    base = base.mod(modulus); // 先对base取模，减少后续计算量
    while (exponent.compareTo(BigInteger.ZERO) > 0) {
        // 判断当前位是否为1
        if (exponent.mod(BigInteger.TWO).equals(BigInteger.ONE)) {
            result = result.multiply(base).mod(modulus);
        }
        exponent = exponent.divide(BigInteger.TWO);
        base = base.multiply(base).mod(modulus);
    }
    return result;
}

内容的提问来源于stack exchange，提问作者David Rowland