转换为 BigInteger

Question

我想把这个函数代码重写为Java中的

BigInteger

类：

 static int power(int x, int y, int p)
    {
        int res = 1; // Initialize result
 
        while (y > 0) {
 
            // If y is odd, multiply x with result
            if ((y & 1) != 0)
                res = res * x;
 
            // y must be even now
            y = y >> 1; // y = y/2
            x = x * x; // Change x to x^2
        }
        return res % p;
    }

我尝试并编写了以下代码：

static BigInteger power(BigInteger x, BigInteger y, BigInteger p) {
        BigInteger res = BigInteger.ONE; // Initialize result

        while (y.compareTo(BigInteger.ZERO) == 1) {   

            // If y is odd, multiply x with result
            if ((y.and(BigInteger.ONE)) != BigInteger.ZERO)  
                res = res.multiply(x);  

            // y must be even now
            y = y.shiftRight(1); // y = y/2   
            x = x.multiply(x); // Change x to x^2
        }
        return res.mod(p);
    }

但是当我测试输入“power(2, 5, 13)”时，输出是11，然而，正确答案是6。

我把自己写的代码检查了好几遍，也没找到问题所在。你能帮我输出正确的答案代码吗？

Answer 1

您应该将引用类型与

.equals

进行比较，而不是像基元那样与

==

进行比较。

if (!BigInteger.ZERO.equals(y.and(BigInteger.ONE)))

此外，只需考虑

compareTo

结果的符号即可；不要直接与 1 这样的固定值进行比较。

while (y.compareTo(BigInteger.ZERO) > 0)

Answer 2

该方法已实现为

BigInteger.modPow(BigInteger, BigInteger)

。我会这样称呼它，比如

static BigInteger power(BigInteger x, BigInteger y, BigInteger p) {
    return x.modPow(y, p);
}

其次，您无法使用三个

int

值调用该方法。你需要

BigInteger

参数。就像，

public static void main(String[] args) {
    System.out.println(power(BigInteger.valueOf(2),
            BigInteger.valueOf(5),
            BigInteger.valueOf(13)));
}

我明白了

6