java - long mod 操作返回 int Java

Question

所以我正在使用我在维基百科上看到的这种模幂算法，对于小数字来说它对我来说效果很好。但是当我使用更大的数字(例如 7000000000)时，它总是返回 0。

public static void main(String[] args) {
    System.out.println(modPow(2L, 7000000000L - 1L, 7000000000L));
}

public static long modPow(long base, long exponent, long modulus) {
    long result = 1L;
    base = base % modulus;
    while(exponent > 0) {
        if(exponent % 2 == 1) {
            result = (result * base) % modulus;
        }
        exponent = exponent >> 1;
        System.out.println(result);
        base = (base*base) % modulus;
    }
    return result;
}

我将问题追溯到结果变量，因为函数循环它具有值:

2
8
128
32768
2147483648
-4854775808
0
0
...0s onward

这清楚地表明结果变量被存储为 int，但我已明确将其定义为 long。我尝试在所有计算中添加(长)，以防由于某种原因将其转换为 int，但这不起作用。

这可能是我缺少的一些简单或基本的东西，但我不明白为什么这不起作用。任何帮助是极大的赞赏。

Answer 1

您的结果 * base 溢出long。

在 if 中添加类似以下语句的内容

System.out.println("result * base = " + result*base);`

你会看到:

result * base = 2
2
result * base = 8
8
result * base = 128
128
result * base = 32768
32768
result * base = 2147483648
2147483648
result * base = -9223372036854775808
-4854775808

请注意，Long.MAX_VALUE 为 9223372036854775807