为什么在第47个斐波那契数后返回负数？

Question

我写了一个程序来存储斐波那契数列，并将检索第n个斐波那契数。它一直运行良好，直到第50个斐波那契数，返回一个负数。

getFibonacci(47) 返回1836311903，但是
getFibonacci(48) 返回-1323752223。为什么会这样？

public class Fibonacci {
    static HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

    public static void main(String[] args) {
        int x;
        storeFibonacciNumbers(50);
        System.out.println(getFibonacci(48));
    }

    public static void storeFibonacciNumbers (int n){
        for (int x=1; x <= n; x++ ){
            if(x == 1){
                map.put(x, 0);
            }
            else if (x == 2) {
                map.put(x, x-1);
            }
            else
                map.put(x, map.get(x-1) + map.get(x-2));
        }
    }

    public static long getFibonacci (int x){
        return map.get(x);
    }
}

- Jay King

---

http://en.wikipedia.org/wiki/Integer_overflow - David

Answer 1

这是因为已经达到了Integer的最大值。当你尝试向其中添加一个值时，会发生溢出并“环绕”到负数。

另一种选择是使用支持更高最大值的类型（例如Long）。

在某些情况下，您可能被迫切换到更复杂的类型，但这些类型专门用于存储非常大的整数（例如BigInteger）。

- Philippe Signoret

Answer 2

在HashMap中，您将斐波那契数作为整数存储。 Int可以容纳的最大值是2147483647（2 ^ 31-1） 因此，根据您的计算，Fibonacci（47）必须超过该最大值并发生溢出。

将HashMap值类型更改为Long即可解决问题。

- Thusitha Thilina Dayaratne

Answer 3

一个 整数溢出 是指当算术运算（如乘法或加法）的结果超过用于存储它的整数类型的最大大小时发生的情况。

- Tarek

Answer 4

这是因为 int 类型只能表示到一定的范围。最大值是2147483647，超过这个值后它会重新开始计数。如果你想正确地表示更大的数字，你需要使用不同的数据类型，比如 long。

- shieldstroy

Answer 5

Java中的最大整数是2^31-1或2147483647。一旦达到该值，您将开始返回负数。

您可以使用常量Integer.MAX_VALUE来停止程序，一旦达到该值。

- jriccio

Answer 6

这被称为整数溢出，当一个数字增加到其最大/最小（内存）边界时发生（对于java.lang.Integer来说，这将是-2^31和2^31-1）

- xerx593

---

抱歉，我不是以英语为母语的人...对我来说，即使在堆栈上，溢出也是溢出。 - xerx593