long mod opertaion returns int Java

Question

所以我正在使用我在维基百科某个地方看到的这种模幂算法，它对我来说对小数来说工作得很好。但是当我使用更大的数字（例如 7000000000）时，它总是 returns a 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。我已经尝试将 (long) 添加到所有计算中，以防它出于某种原因将其转换为 int，但这不起作用。

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

Answer 1

您的 result * 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

long mod opertaion returns int Java

long mod opertaion returns an int Java

java

types

casting

long-integer

modular-arithmetic