Perché questo lungo traboccare a -1, invece del valore minimo per il tipo?

Question

Ho il seguente codice che restituisce il numero di nodi in un albero, quando un albero completo binaria è layer strati di altezza:

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

La cosa strana è che quando ho ingresso 63 nella funzione (il valore minimo che produce questo), mi restituisce -1. A 62 restituisce 9223372036854775807, quindi questo sembra essere causato da un overflow.

Non dovrebbe restituirmi il valore minimo di Java lungo + l'importo da cui è stato sovraccaricato? Indipendentemente dall'input che gli ho dato (passato 62), restituirà sempre -1 invece di un numero apparentemente casuale che mi aspetterei da un overflow.

Non sono completamente sicuro di come eseguire il debug di questo, poiché è ricorsivo e il valore a cui sono interessato verrà valutato solo dopo che la funzione ha raggiunto il caso base.

Answer 1

Sei corretto, si tratta di un errore di overflow di un intero con segno a 64 bit. La ragione per cui va a -1 invece del valore intero minimo è perché la stai raddoppiando, non semplicemente aggiungendone una.

9223372036854775807 in Two's Complement dista 63 1 s:

0111 1111 ... 1111 1111 

Per raddoppiare in binario, è sufficiente effettuare uno spostamento a sinistra:

1111 1111 ... 1111 1110 

Tuttavia, questo numero in complemento a due non è il doppio 9223372036854775807, ma piuttosto -2. Quindi, naturalmente, aggiungi 1 a quello prima di tornare per ottenere il risultato -1.

Answer 2

In realtà, si sta restituendo l'importo corretto. E 'solo che "l'importo che era straripato da" è esattamente a destra per rendere la risposta -1 :)

Considerate questo:
Il numero di nodi in un albero binario completo è 2^n - 1 per n strati. Di qui la sua rappresentazione binaria è 0000...00111...111 dove il numero di 1 s è proprio il numero di strati meno 1. Non appena si raggiunge la lunghezza del long sei bloccato al tronco 11...11, che è appunto -1

Answer 3

Preferisco sempre le visualizzazioni con cose come questa.

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

Dove n è 9223372036854775807 - il valore di avere a destra prima di moltiplicare per 2. Invece di moltiplicazione, però, pensa di esso come aggiunta. n + n. Vedendolo su una linea numerica, puoi vedere che finirai a -2. Stai praticamente traboccando oltre la maggior parte dei numeri negativi.

In modo che la mia risposta contribuisca a qualcosa di significativo rispetto agli altri, uno strumento utile in situazioni come questa è di suddividere l'aritmetica in più righe per eseguire il debug.Si potrebbe scrivere:

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

Stai essenzialmente far rispettare ordine-di-operazioni come ci si aspetta che (che può aiutarvi a realizzare il programma sta facendo le cose fuori l'ordine che si desidera loro in), ma ti permette anche di andare nel debugger e vedere i valori intermedi dei tuoi calcoli. Qui avresti notato b == -2. Perché è b == -2? Beh, deve essere perché 2 * a == -2, ecc.