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

Question

当完整的二叉树 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(产生这个的最小值)时，它返回了 -1。在62，它返回9223372036854775807，所以这似乎是由溢出引起的。

难道不应该把 Java 的 long 的最小值 + 溢出的数量还给我吗？不管我给它的输入是什么(通过 62)，它总是会返回 -1 而不是我期望溢出的看似随机的数字。

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

Answer 1

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

9223372036854775807 in Two's Complement是 63 1s:

0111 1111 ... 1111 1111

要以二进制形式加倍，只需执行左移:

1111 1111 ... 1111 1110

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