Почему это длинное переполнение до -1, а не минимальное значение для типа?

У меня есть следующий код, который возвращает количество узлов в дереве, когда полное двоичное дерево имеет 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 вместо кажущегося случайного числа, которое я ожидал бы от переполнения.

Я не совсем уверен, как отлаживать это, поскольку он рекурсивный, и интересующее меня значение будет оцениваться только после того, как функция достигнет базового.

Ответы

Ответ 1

Вы правы, это ошибка переполнения 64-разрядного целого числа со знаком. Причина, по которой он переходит на -1 вместо минимального целочисленного значения, заключается в том, что вы удваиваете его, а не просто добавляете его.

9223372036854775807 в Два дополнения - 63 1 s:

0111 1111 ... 1111 1111

Чтобы удвоить его в двоичном формате, просто выполните сдвиг влево:

1111 1111 ... 1111 1110

Однако это число в Two Complement не дважды 9223372036854775807, а скорее -2. Затем, конечно, вы добавляете 1 к этому, прежде чем вернуться, чтобы получить результат -1.

Ответ 2

Фактически, он возвращает вам правильную сумму. Это просто, что "количество, которое было переполнено", точно соответствует ответу -1:)

Рассмотрим это:
Число узлов в полном двоичном дереве 2^n - 1 для n слоев. Следовательно, его двоичное представление 0000...00111...111, где число 1 - это точно количество слоев минус 1. Как только вы достигнете длины long, вы застряли на усеченном 11...11, что точно -1

Ответ 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 и т.д.