为什么这个 long 溢出到 -1，而不是类型的最小值？

Question

我有以下代码，当完整的二叉树是 layer 层高时，return 是树中的节点数：

public static long nNodesUpToLayer(int layer) {
        if (layer < 0) throw new IllegalArgumentException(
            "The layer number must be positive: " + layer );

        //At layer 0, there must be 1 node; the root.
        if (layer == 0) return 1;

        //Else, there will be 1 + 2 * (the number of nodes in the previous layer) nodes.
        return 1 + (2 * nNodesUpToLayer(layer - 1));

奇怪的是，当我在函数中输入 63（产生这个的最小值）时，它会返回 -1。在62，它返回9223372036854775807，所以这似乎是由溢出引起的。

它不应该给我返回Java的多头的最小值+溢出的数量吗？不管我给它的输入是什么（通过 62），它总是 return -1 而不是我期望溢出的看似随机的数字。

我不完全确定如何调试它，因为它是递归的，而且我感兴趣的值只有在函数达到基本情况后才会被评估。

Answer 1

实际上，它返回给您的金额是正确的。只是 "the amount that it was overflowed by" 完全正确地做出了答案 -1 :)

考虑一下：
n 层的完全二叉树中的节点数为 2^n - 1。因此，它的二进制表示是 0000...00111...111，其中 1 的数量恰好是层数减去 1。一旦达到 long 的长度，您就会被截断11...11，也就是-1

Answer 2

你是对的，这是一个64位有符号整数的溢出错误。它转到 -1 而不是最小整数值的原因是因为你将它加倍，而不是简单地加一个。

9223372036854775807 在 Two's Complement 中是 63 1s:

0111 1111 ... 1111 1111

要将其以二进制形式加倍，只需执行左移即可：

1111 1111 ... 1111 1110

然而，这个数字在二进制补码中不是 9223372036854775807 的两倍，而是 -2。然后，当然，在返回之前添加 1 以获得 -1 结果。

Answer 3

我总是喜欢这样的可视化效果。

                      (min long)
                      v 
<--------------------||--------------------------------------->
                     ^                                   ^
               (max long, n)                            -1

其中 n 是 9223372036854775807 - 乘以 2 之前的值。不过，与其乘法，不如将其视为加法。 n + n。通过在数轴上查看它，您可以看到您最终处于 -2。您基本上已经超过了大部分负数。

因此，与其他答案相比，我的答案有所贡献，在这种情况下，一个有用的工具是将您的算法分成多行以便调试。你可以这样写：

int a = nNodesUpToLayer(layer - 1);
int b = 2 * a;
int c = 1 + b;
return c;

您实际上是在按照您的预期执行操作顺序（这可能会帮助您意识到程序正在按照您希望的顺序执行操作），但它也让您进入调试器并查看计算的中间值。在这里你会注意到 b == -2。为什么是 b == -2？嗯，一定是因为2 * a == -2，等等

为什么这个 long 溢出到 -1，而不是类型的最小值？

Why is this long overflowing to -1, instead of the minimum value for the type?

java

integer

integer-overflow

biginteger