Java Longs 中的斐波那契计算显示负值

Question

我的斐波那契计算器工作正常，但是当数字上升到更高时，结果会变成负数，就像它超过最大值

Integer

一样。

它正在使用缓存

java.util.Map<Integer, Long>

。

Map

中的所有内容都完全符合预期，但是当打印出来时，我得到例如对于 291:

-784134397488903422

根据http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibCalcX.html，应该是：

2923602405716568564338475449381171413803636207598822186175234

我的

Long

似乎出了点问题，但我还不确定到底是什么。有人可以指出我正确的方向吗？

Map

条目的值： http://pastebin.com/uje07Ays

Answer 1

我认为您超过了 Java 用于 long 类型的有符号 64 位整数中可以存储的最大 long 值，有关 Long 的更多信息以及 Java API 中的这些信息：http://docs.oracle.com/javase /7/docs/api/java/lang/Long.html。

The maximum positive value for a 64 bits signed integer is 2^63 -1:

9 223 372 036 854 775 807

，你的值似乎已经达到这个限制，如果有符号整数的最高位是1，那么有符号整数变成负数（见2 补整数更多细节：http://en.wikipedia.org/wiki/Two%27s_complement).

您需要使用 BigInteger 来获得任意精度的整数http://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html.

Answer 2

java有8种原始数据类型

字节

• 最小值为-128 (-2^7)
• 最大值为127（含）（2^7 -1）
• 默认值为 0

短

• 最小值为 -32,768 (-2^15)
• 最大值为32767（含）（2^15 -1）
• 默认值为 0.
• short 数据类型也可以作为byte 数据类型来保存内存。 short 比 int 小 2 倍（但是 java 把这个类型改成 int 来计算）

int

• 最小值为 - 2,147,483,648.(-2^31)
• 最大值是2,147,483,647(含).(2^31 -1) ，比你的数字还多
• Int 一般用作整数值的默认数据类型 除非担心内存。
• 默认值为0。

长

• 最小值为-9,223,372,036,854,775,808.(-2^63)
• 最大值为9,223,372,036,854,775,807（含）。 (2^63 -1) 这个值小于你的数字
• 当需要比 int 更宽的范围时使用此类型。
• 默认值为 0L。

浮动

• Float 数据类型是单精度 32 位 IEEE 754 浮点数。
• Float 主要用于在大型浮点数组中节省内存 数字。使用这种类型的 int 值是犯罪
• 默认值为 0.0f.

双

• double 数据类型是双精度 64 位 IEEE 754 浮点数 点。
• 这种数据类型一般作为decimal的默认数据类型 值，通常是默认选择。
• Double 数据类型不应该用于精确值，例如 货币。
• 默认值为 0.0d。

布尔值

• 布尔数据类型代表一位信息。
• 只有两个可能的值：真和假。
• 此数据类型用于跟踪真/假的简单标志 条件。
• 默认值为假。

炭

• har 数据类型是单个 16 位 Unicode 字符。
• 最小值为 '\u0000'（或 0）。
• 最大值为 '\uffff'（或 65,535，包括在内）。
• Char 数据类型用于存储任何字符。

如您所见，以上类型都不能存储您的值，因此您必须使用 BigInteger（example）或任何其他可以处理这个大值的类。

Answer 3

public static void main(String[] args)
    {
        Map<Integer, BigDecimal> fibonacciMap = new HashMap<Integer, BigDecimal>();
        fibonacciMap.put(1, BigDecimal.valueOf(1));
        fibonacciMap.put(2, BigDecimal.valueOf(1));
        System.out.println(1 + " : " + fibonacciMap.get(1));
        System.out.println(2 + " : " + fibonacciMap.get(2));

        for(int i=3;i<=300;i++)
        {
            fibonacciMap.put(i, fibonacciMap.get(i-1).add(fibonacciMap.get(i-2)));
            System.out.println(i + " : " + fibonacciMap.get(i));
        }
    }

因为，long 在 java 中的最大值是 9223372036854775807。因此，当斐波那契数超过这个最大值时，它开始从 -9223372036854775808（最小值）到零到 9223372036854775807（最大值）四舍五入。因此，我们需要使用 BigDecimal 而不是 Long 来避免 -ve 值。

例如：

Fib[92]=7540113804746346429

Fib[91]=4660046610375530309

(BigDecimal)Fib[93]=Fib[91]+Fib[92]=12200160415121876738 大于 Long.MAX_VALUE

(长)Fib[93]= -6246583658587674878

Long.MAX_VALUE = 9223372036854775807

Long.MIN_VALUE = -9223372036854775808

所以， (BigDecimal)Fib[93] = Long.MAX_VALUE - (Long.MIN_VALUE - (Long)Fib[93]) + 1;