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

I have the following code that returns the number of nodes in a tree when a complete Binary Tree is layer layers tall:

我有以下代码,当完整的二进制树是图层高时,它返回树中的节点数:

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));

The odd thing is, when I input 63 into the function (the minimum value that produces this), it gives me back -1. At 62, it gives back 9223372036854775807, so this seems to be caused by an overflow.

奇怪的是,当我输入63进入函数(产生这个的最小值)时,它给了我-1。在62,它返回9223372036854775807,所以这似乎是由溢出引起的。

Shouldn't it give me back the minimum value of Java's long + the amount that it was overflowed by? Regardless of the input that I give it though (passed 62), it will always return -1 instead of a seemingly random number that I'd expect from an overflow.

难道它不能给我回Java长期的最小值+它溢出的数量?无论我给它的输入(通过62),它总是会返回-1而不是一个看似随机的数字,我期望从溢出。

I'm not entirely sure how to debug this, since it's recursive, and the value I'm interested in will only be evaluated once the the function has reached the base-case.

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

3 个解决方案

#1

You are correct, it is an overflow error of a 64 bit signed integer. The reason it goes to -1 instead of the minimum integer value is because you are doubling it, not simply adding one.

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

9223372036854775807 in Two's Complement is 63 1s:

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

0111 1111 ... 1111 1111

To double it in binary, simply perform a left shift:

要以二进制加倍,只需执行左移:

1111 1111 ... 1111 1110

However, this number in Two's Complement is not twice 9223372036854775807, but rather -2. Then, of course, you add 1 to that before returning to get your -1 result.

但是,Two's Complement中的这个数字不是两倍9223372036854775807,而是-2。然后,当然,在返回获得-1结果之前,先添加1。

#2

Actually, it is returning you the correct amount. It's just that "the amount that it was overflowed by" is exactly right to make the answer -1 :)

实际上,它会返回正确的金额。只是“它溢出的数量”是完全正确的答案-1 :)

Consider this:
The number of nodes in a complete binary tree is 2^n - 1 for n layers. Hence its binary representation is 0000...00111...111 where the number of 1s is precisely the number of layers minus 1. As soon as you reach the length of the long you're stuck at the truncated 11...11, which is precisely -1

考虑一下:对于n个层,完整二叉树中的节点数为2 ^ n - 1。因此它的二进制表示是0000 ... 00111 ... 111,其中1的数量恰好是层数减去1.一旦达到长度的长度,你就被卡在截断的11 ... 11 ,这正好是-1

#3

I always prefer the visualizations with things like this.

我总是喜欢用这样的东西进行可视化。

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

Where n is 9223372036854775807 - the value you have right before you multiply by 2. Instead of multiplication, though, think of it as addition. n + n. By seeing it on a number line, you can see that you'd end up at -2. You're basically overflowing past most of the negative numbers.

其中n是9223372036854775807 - 在乘以2之前的值。而不是乘法,而是将其视为加法。 n + n。通过在数字线上看到它,你可以看到你最终在-2。你基本上已经超过了大多数负数。

So that my answer contributes something meaningful compared to the others, one helpful tool in situations like this is to break your arithmetic into multiple lines in order to debug. You could write:

因此,与其他人相比,我的答案提供了一些有意义的东西,在这种情况下,一个有用的工具是将算术分成多行以便进行调试。你可以写:

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

You're essentially enforcing order-of-operations as you'd expect it(which may help you realize the program is doing things out of the order you want them in), but it also lets you go into the debugger and see the intermediate values of your calculations. Here you would have noticed b == -2. Why is b == -2? Well, it must be because 2 * a == -2, etc.

你基本上按照你的预期强制执行操作顺序(这可能会帮助你实现程序按照你想要的顺序执行操作),但它也允许你进入调试器并看到中间件你的计算值。在这里你会注意到b == -2。为什么b == -2?好吧,一定是因为2 * a == -2等

#1