Warum ist dieser lange Überlauf auf -1, anstelle des Mindestwerts für den Typ?

Question

Ich habe den folgenden Code, der die Anzahl von Knoten in einem Baum zurückgibt, wenn eine vollständige Binary Tree layer Schichten groß ist:

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

Das Seltsame ist, wenn ich Eingang 63 in die Funktion (der minimale Wert, produziert dies), gibt es mir -1 zurück. Bei 62 gibt es 9223372036854775807 zurück, so dass dies durch einen Überlauf verursacht wird.

Sollte es mir nicht lange + die Menge der Minimalwert von Java zurückgeben, die sie durch überschwemmt wurde? Unabhängig von der Eingabe, die ich es gebe (bestanden 62), wird es immer -1 anstelle einer scheinbar zufälligen Zahl, die ich von einem Überlauf erwarten würde.

Ich bin nicht ganz sicher, wie dies zu debuggen, da es rekursiv ist, und der Wert Ich habe Interesse an wird nur ausgewertet werden, wenn die die Funktion des Basis-Fall erreicht hat.

Answer 1

Sie sind richtig, es ist ein Überlauffehler einer 64-Bit-Ganzzahl mit Vorzeichen. Der Grund dafür, dass es -1 anstelle des minimalen Integer-Wertes ist, liegt daran, dass Sie es verdoppeln, nicht einfach eins hinzufügen.

9223372036854775807 in Two's Complement ist 63 1 s:

0111 1111 ... 1111 1111 

es in binären Um zu verdoppeln, führen einfach eine Linksverschiebung:

1111 1111 ... 1111 1110 

jedoch diese Zahl in Complement Twos ist nicht zweimal 9223372036854775807, aber eher -2. Dann fügen Sie natürlich 1 hinzu, bevor Sie zurückkehren, um Ihr -1 Ergebnis zu erhalten.

Answer 2

Eigentlich ist es kehrt Sie die richtige Menge. Es ist nur so, dass „die Menge, die sie durch überschwemmt wurde“ genau richtig die Antwort -1 :)

das Betrachten zu machen:
Die Anzahl der Knoten in einem vollständigen binären Baum ist 2^n - 1 für n Schichten. Daher ihre binäre Darstellung ist 0000...00111...111 wo die Zahl der 1 s genau die Anzahl der Schichten ist minus 1. Sobald Sie die Länge der Reichweite long Sie auf dem abgeschnittenen 11...11, stecken die gerade -1

Answer 3

Ich ziehe immer die Visualisierungen mit Dingen wie diese.

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

Wo n ist 9223372036854775807 - der Wert, den Sie Recht haben, bevor Sie mit dem 2. Anstelle der Multiplikation multiplizieren, aber betrachten Sie es als Zugabe. n + n. Wenn Sie es in einer Zahlenzeile sehen, können Sie sehen, dass Sie bei -2 enden. Sie sind im Grunde über die meisten der negativen Zahlen überfüllt.

Damit meine Antwort etwas Sinnvolles im Vergleich zu den anderen trägt, ein hilfreiches Werkzeug in Situationen wie dieser ist Ihre Arithmetik in mehrere Zeilen, um zu debuggen zu brechen.Man könnte schreiben:

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

Sie sind im Wesentlichen um-of-Operationen durchzusetzen, wie Sie es erwarten würden (was kann Ihnen helfen, das Programm macht die Dinge aus der Bestellung Sie wollen, dass sie in klar), aber es Sie können auch in den Debugger gehen und die Zwischenwerte Ihrer Berechnungen sehen. Hier hätten Sie bemerkt b == -2. Warum ist b == -2? Nun, es muss sein, weil 2 * a == -2, etc.