multiplicar - cast biginteger to integer java

¿Por qué este desbordamiento largo a-1, en lugar del valor mínimo para el tipo?

Question

Tengo el siguiente código que devuelve la cantidad de nodos en un árbol cuando un árbol binario completo tiene layer capas altas:

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

Lo curioso es que cuando ingreso 63 a la función (el valor mínimo que produce esto), me devuelve -1 . En 62 , devuelve 9223372036854775807 , así que esto parece ser causado por un desbordamiento.

¿No debería devolverme el valor mínimo de Java + la cantidad por la que se desbordó? Independientemente de la entrada que le dé (pase 62 ), siempre devolverá -1 lugar de un número aparentemente aleatorio que esperaría de un desbordamiento.

No estoy del todo seguro de cómo depurar esto, ya que es recursivo, y el valor que me interesa solo se evaluará una vez que la función haya alcanzado el caso base.

Answer 1

En realidad, te devuelve la cantidad correcta. Es solo que "la cantidad por la que se desbordó" es exactamente correcto para dar la respuesta -1 :)

Considera esto:
La cantidad de nodos en un árbol binario completo es 2^n - 1 para n capas. Por lo tanto, su representación binaria es 0000...00111...111 donde el número de 1 s es precisamente el número de capas menos 1. Tan pronto como alcances la longitud del long estarás atrapado en el 11...11 truncado 11...11 , que es precisamente -1

Answer 2

Está en lo cierto, es un error de desbordamiento de un entero con signo de 64 bits. La razón por la que va a -1 lugar del valor entero mínimo es porque la está doblando, no simplemente agregando una.

9223372036854775807 en Complemento Dos es 63 1 s:

0111 1111 ... 1111 1111

Para duplicarlo en binario, simplemente realice un cambio a la izquierda:

1111 1111 ... 1111 1110

Sin embargo, este número en Two''s Complement no es dos veces 9223372036854775807 , sino más bien -2 . Luego, por supuesto, agregas 1 a eso antes de volver para obtener tu -1 resultado.

Answer 3

Siempre prefiero las visualizaciones con cosas como esta.

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

Donde n es 9223372036854775807 - el valor que tiene justo antes de multiplicar por 2. En lugar de la multiplicación, piense en ello como una suma. n + n . Al verlo en una recta numérica, puede ver que terminaría en -2. Básicamente estás rebasando la mayoría de los números negativos.

Para que mi respuesta contribuya con algo significativo en comparación con los demás, una herramienta útil en situaciones como esta es dividir su aritmética en varias líneas para depurar. Podrías escribir:

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

En esencia, estás aplicando el orden de las operaciones como lo esperarías (lo que puede ayudarte a darte cuenta de que el programa está haciendo las cosas fuera del orden en que las quieres), pero también te permite acceder al depurador y ver el intermedio valores de tus cálculos. Aquí habrías notado b == -2 . ¿Por qué es b == -2 ? Bueno, debe ser porque 2 * a == -2 , etc.