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

integer java integer-overflow biginteger

2022-09-01 13:38:39

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

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-1629223372036854775807

难道它不应该给我返回Java的long的最小值+它被溢出的量吗？无论我给它输入（通过），它总是会返回，而不是我期望从溢出中获得的看似随机的数字。62-1

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

答案 1

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

9223372036854775807在 Two 的补码中是 63 s：1

0111 1111 ... 1111 1111

要将其加倍为二进制，只需执行左移：

1111 1111 ... 1111 1110

然而，二的补数中的这个数字不是两次，而是。然后，当然，在返回以获得结果之前，您可以添加该内容。9223372036854775807-21-1

答案 2

实际上，它正在返回正确的金额。只是“它被溢出的量”是完全正确的，使答案:)-1

请考虑以下情况：
完整二叉树中的节点数是层。因此，它的二进制表示是其中的s个数恰好是层数减去1。一旦你到达的长度，你就会卡在截断处，这恰恰是2^n - 1n0000...00111...1111long11...11-1