为什么 2 的 31 次方在此 Java 函数中返回负数？

Question

作业：

Write a recursive function recPow that computes 2n for n >= 0 in Java. The function will have the following profile:

public static int recPow(int n)

The function must consider all cases and be tested exhaustively.

我的问题

我不明白为什么当我输入 recPow(31) 而不是 2147483648 时我的代码 returns -2147483648。我知道你们中的一些人可能会告诉我改用 long 而不是 int，但是我相信由于作业的冗长，我需要坚持使用 int。我从来都不是很好的计算数字，如果有人能帮助我理解为什么会发生这种情况，我将非常感激。

此外 - 更大的指数 return 0（不过我认为这可能与我们需要使用整数与长整数的事实有关。）

我的代码

public static int baseNum = 2, powResult = 1;

public static int recPow(int n) {
    //if the int is not bigger than 0 
    //must only accept ints
    if (n < 0) {
        throw new IllegalArgumentException("n has to be > 0");
    } else {
        //recursion here
        //base number = 2
        if (n==0) {
            return powResult;
        } else {
            powResult = powResult * baseNum;
            return recPow(n - 1);
        }
    }
}

Answer 1

larger exponents return 0 (however I think this may have to do with the fact that we need to use ints vs longs.)

正确。

int i = (int) 2147483648L; // -2147483648 due to over flow
int j = i * 2; // 0 due to overflow.

您可以使用 long，但这有同样的问题，但需要更高的值。

public static long recPower(int baseNum, int power) {
    if (power < 0) throw new IllegalArgumentException();
    return power == 0 ? 1L : baseNum * recPower(baseNum, power - 1);
}

检查溢出的一种方法是查看

public static long recPower(int baseNum, int power) {
    if (power < 0) throw new IllegalArgumentException();
    return power == 0 ? 1L : baseNum * recPower(baseNum, power - 1);
}

或检查溢出

public static long recPower(int baseNum, int power) {
    if (power < 0) throw new IllegalArgumentException();
    return power == 0 ? 1L 
           : Math.multiplyExact(baseNum, recPower(baseNum, power - 1));
}

您可以使用 BigInteger，它的限制要大得多。

Answer 2

这是由于 int 数据类型的溢出。

Java的int大小是32位，所以范围是-2,147,483,648到2,147,483,647。

2^31 = 2147483648

所以溢出到-2147483648 因为 2,147,483,647 的二进制值是 01111111111111111111111111111111（一个零和 31 个一），其中第一位是 "sign bit"（2 的补码形式）。

如果您尝试超出此限制 (2,147,483,647) 1（即向其加 1），它会将符号位更改为 1，从而使此 int 为负数。

所以它会变成 10000000000000000000000000000000（1 个一和 31 个零），给你答案 -2147483648。

为什么 2 的 31 次方在此 Java 函数中返回负数？

Why is 2 to the power of 31 returning a negative in this Java function?

java

tail-recursion

negative-number

pow