Warum gibt i = i + i mir 0?

96

Ich habe ein einfaches Programm:

public class Mathz {
    static int i = 1;
    public static void main(String[] args) {    
        while (true){
            i = i + i;
            System.out.println(i);
        }
    }
}

Als ich dieses Programm ausführen, alles , was ich sehe , ist 0für iin meiner Ausgabe. Ich hätte das erste Mal erwartete Runde haben wir würden i = 1 + 1, gefolgt von i = 2 + 2, gefolgt von i = 4 + 4usw.

Liegt das daran, dass ider Wert auf den Wert zurückgesetzt wird, sobald wir versuchen, ihn auf der linken Seite erneut zu deklarieren 0?

Wenn mich jemand auf die Einzelheiten hinweisen kann, wäre das großartig.

Ändern Sie das intin longund es scheint, als würden Zahlen wie erwartet gedruckt. Ich bin überrascht, wie schnell es den maximalen 32-Bit-Wert erreicht!

DeaIss
quelle

Antworten:

168

Das Problem ist auf einen Ganzzahlüberlauf zurückzuführen.

In 32-Bit-Zweierkomplement-Arithmetik:

iEs beginnt zwar mit Zweierpotenzwerten, aber dann beginnt das Überlaufverhalten, sobald Sie 2 30 erreicht haben :

2 30 + 2 30 = -2 31

-2 31 + -2 31 = 0

... in der intArithmetik, da es im Wesentlichen arithmetische Mod 2 ^ 32 ist.

Louis Wasserman
quelle
28
Könnten Sie Ihre Antwort etwas erweitern?
DeaIss
17
@oOTesterOo Es beginnt mit dem Drucken von 2, 4 usw., aber es erreicht sehr schnell den Maximalwert der ganzen Zahl und "umschließt" negative Zahlen. Sobald es Null erreicht, bleibt es für immer bei Null
Richard Tingle
52
Diese Antwort ist nicht einmal vollständig (es nicht einmal erwähnen , dass der Wert wird nicht sein , 0auf den ersten paar Iterationen, aber die Geschwindigkeit der Ausgabe wird diese Tatsache von den OP Verschleierung). Warum wird es akzeptiert?
Leichtigkeitsrennen im Orbit
16
Vermutlich wurde es akzeptiert, weil es vom OP als hilfreich angesehen wurde.
Joe
4
@LightnessRacesinOrbit Obwohl die Probleme, die das OP in seine Frage gestellt hat, nicht direkt angesprochen werden, enthält die Antwort genügend Informationen, damit ein anständiger Programmierer ableiten kann, was los ist.
Kevin
334

Einführung

Das Problem ist ein ganzzahliger Überlauf. Wenn es überläuft, kehrt es zum Minimalwert zurück und fährt von dort fort. Wenn es unterläuft, kehrt es zum Maximalwert zurück und fährt von dort fort. Das Bild unten zeigt einen Kilometerzähler. Ich benutze dies, um Überläufe zu erklären. Es ist ein mechanischer Überlauf, aber immer noch ein gutes Beispiel.

In einem Kilometerzähler, der max digit = 9über das Maximum hinausgeht 9 + 1, überträgt und gibt ein 0; Es gibt jedoch keine höhere Ziffer, die in a geändert werden kann 1, sodass der Zähler auf zurückgesetzt wird zero. Sie haben die Idee - "Integer Overflows" kommen jetzt in den Sinn.

Geben Sie hier die Bildbeschreibung ein Geben Sie hier die Bildbeschreibung ein

Das größte Dezimalliteral vom Typ int ist 2147483647 (2 31 -1). Alle Dezimalliterale von 0 bis 2147483647 können überall dort erscheinen, wo ein int-Literal erscheinen kann, aber das Literal 2147483648 kann nur als Operand des unären Negationsoperators erscheinen -.

Wenn eine ganzzahlige Addition überläuft, sind das Ergebnis die niederwertigen Bits der mathematischen Summe, wie sie in einem ausreichend großen Zweierkomplementformat dargestellt werden. Wenn ein Überlauf auftritt, stimmt das Vorzeichen des Ergebnisses nicht mit dem Vorzeichen der mathematischen Summe der beiden Operandenwerte überein.

Somit 2147483647 + 1läuft über und wickelt sich um -2147483648. Daher int i=2147483647 + 1wäre übergelaufen, was nicht gleich ist 2147483648. Außerdem sagen Sie "es wird immer 0 gedruckt". Dies ist nicht der Fall, da http://ideone.com/WHrQIW . Unten zeigen diese 8 Zahlen den Punkt, an dem es schwenkt und überläuft. Es beginnt dann, Nullen zu drucken. Seien Sie auch nicht überrascht, wie schnell es berechnet, die Maschinen von heute sind schnell.

268435456
536870912
1073741824
-2147483648
0
0
0
0

Warum ein ganzzahliger Überlauf "umhüllt"

Original PDF

Ali Gajani
quelle
17
Ich habe die Animation für "Pacman" zu symbolischen Zwecken hinzugefügt, aber sie dient auch als großartige visuelle Darstellung, wie man "ganzzahlige Überläufe" sehen würde.
Ali Gajani
9
Dies ist meine Lieblingsantwort auf dieser Seite aller Zeiten.
Lee White
2
Sie scheinen übersehen zu haben, dass dies eine Verdopplungssequenz war, ohne eine hinzuzufügen.
Paŭlo Ebermann
2
Ich denke, die Pacman-Animation hat diese Antwort mehr positiv bewertet als die akzeptierte Antwort. Haben Sie eine weitere positive Bewertung für mich - es ist eines meiner Lieblingsspiele!
Husman
3
Für alle, die die Symbolik nicht verstanden haben: en.wikipedia.org/wiki/Kill_screen#Pac-Man
wei2912
46

Nein, es werden nicht nur Nullen gedruckt.

Wenn Sie dies ändern, werden Sie sehen, was passiert.

    int k = 50;
    while (true){
        i = i + i;
        System.out.println(i);
        k--;
        if (k<0) break;
    }

Was passiert, nennt man Überlauf.

peter.petrov
quelle
61
Interessante Möglichkeit, eine for-Schleife zu schreiben :)
Bernhard
17
@Bernhard Es ist wahrscheinlich, die Struktur des OP-Programms beizubehalten.
Taemyr
4
@Taemyr Wahrscheinlich, aber dann hätte er ersetzt truemit i<10000:)
Bernhard
7
Ich wollte nur ein paar Aussagen hinzufügen; ohne irgendwelche Anweisungen zu löschen / zu ändern. Ich bin überrascht, dass es so große Aufmerksamkeit auf sich gezogen hat.
Peter.petrov
18
Sie hätten den versteckten Operator while(k --> 0)umgangssprachlich "while kgoes to 0" verwenden können;)
Laurent LA RIZZA
15
static int i = 1;
    public static void main(String[] args) throws InterruptedException {
        while (true){
            i = i + i;
            System.out.println(i);
            Thread.sleep(100);
        }
    }

Ausgabe:

2
4
8
16
32
64
...
1073741824
-2147483648
0
0

when sum > Integer.MAX_INT then assign i = 0;
TrungTran05T3
quelle
4
Ähm, nein, es funktioniert nur für diese bestimmte Sequenz, um auf Null zu kommen. Versuchen Sie mit 3.
Paŭlo Ebermann
4

Da ich nicht genug Ruf habe, kann ich das Bild der Ausgabe für dasselbe Programm nicht in C mit kontrollierter Ausgabe veröffentlichen. Sie können selbst versuchen, zu sehen, dass es tatsächlich 32 Mal gedruckt wird, und dann, wie aufgrund des Überlaufs erläutert, i = 1073741824 + 1073741824 wechselt zu -2147483648 und eine weitere Addition liegt außerhalb des Bereichs von int und dreht sich zu Zero.

#include<stdio.h>
#include<conio.h>

int main()
{
static int i = 1;

    while (true){
        i = i + i;
      printf("\n%d",i);
      _getch();
    }
      return 0;
}
Kaify
quelle
3
Dieses Programm in C löst bei jeder Ausführung ein undefiniertes Verhalten aus, wodurch der Compiler das gesamte Programm durch irgendetwas ersetzen kann (auch wenn system("deltree C:")Sie unter DOS / Windows arbeiten). Der vorzeichenbehaftete Ganzzahlüberlauf ist im Gegensatz zu Java in C / C ++ ein undefiniertes Verhalten. Seien Sie sehr vorsichtig, wenn Sie diese Art von Konstrukt verwenden.
Filcab
@filcab: " Ersetze das ganze Programm durch irgendetwas" wovon redest du ? Ich habe dieses Programm auf Visual Studio 2012 ausgeführt und es läuft perfekt für beide signed and unsignedGanzzahlen ohne undefiniertes Verhalten
Kaify
3
@Kaify: Gut funktionieren ist ein vollkommen gültiges undefiniertes Verhalten. Stellen Sie sich jedoch vor, dass der Code i += ifür mehr als 32 Iterationen ausgeführt wurde if (i > 0). Der Compiler könnte dies optimieren, if(true)da, wenn wir immer positive Zahlen hinzufügen, iimmer größer als 0 sein wird. Er könnte auch die Bedingung belassen, in der sie aufgrund des hier dargestellten Überlaufs nicht ausgeführt wird. Da der Compiler aus diesem Code zwei gleich gültige Programme erstellen kann, ist das Verhalten undefiniert.
3Doubloons
1
@Kaify: Es ist keine lexikalische Analyse, sondern der Compiler, der Ihren Code kompiliert und nach dem Standard „seltsame“ Optimierungen vornehmen kann. Wie die Schleife, über die 3Doubloons gesprochen hat. Nur weil Compiler, die Sie versuchen, immer etwas zu tun scheinen, bedeutet dies nicht, dass der Standard garantiert, dass Ihr Programm immer auf die gleiche Weise ausgeführt wird. Sie hatten ein undefiniertes Verhalten, ein Teil des Codes wurde möglicherweise entfernt, da es keine Möglichkeit gibt, dorthin zu gelangen (UB garantiert dies). Diese Beiträge aus dem llvm-Blog (und die Links dort) enthalten weitere Informationen: blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
filcab
2
@Kaify: Es tut mir leid, dass ich es nicht formuliert habe, aber es ist völlig falsch zu sagen, dass es geheim gehalten wurde, insbesondere wenn es das zweite Ergebnis bei Google für "undefiniertes Verhalten" ist. Dies war der spezifische Begriff, den ich für das verwendet habe, was ausgelöst wurde .
Filcab
4

Der Wert von iwird mit einer festen Anzahl von Binärziffern im Speicher gespeichert. Wenn eine Nummer mehr Ziffern benötigt als verfügbar ist, werden nur die niedrigsten Ziffern gespeichert (die höchsten Ziffern gehen verloren).

Das Hinzufügen izu sich selbst ist dasselbe wie das Multiplizieren imit zwei. Genau wie das Multiplizieren einer Zahl mit zehn in Dezimalschreibweise durch Verschieben jeder Ziffer nach links und Setzen einer Null nach rechts durchgeführt werden kann, kann das Multiplizieren einer Zahl mit zwei in Binärschreibweise auf die gleiche Weise durchgeführt werden. Dadurch wird rechts eine Ziffer hinzugefügt, sodass links eine Ziffer verloren geht.

Hier ist der Startwert 1, wenn wir also 8 Ziffern zum Speichern verwenden i(zum Beispiel),

  • Nach 0 Iterationen ist der Wert 00000001
  • Nach 1 Iteration ist der Wert 00000010
  • Nach 2 Iterationen ist der Wert 00000100

und so weiter bis zum letzten Schritt ungleich Null

  • Nach 7 Iterationen ist der Wert 10000000
  • Nach 8 Iterationen ist der Wert 00000000

Unabhängig davon, wie viele Binärziffern zum Speichern der Nummer zugewiesen sind und wie hoch der Startwert ist, gehen schließlich alle Ziffern verloren, wenn sie nach links verschoben werden. Wenn Sie die Zahl nach diesem Zeitpunkt weiter verdoppeln, ändert sich die Zahl nicht mehr - sie wird weiterhin durch alle Nullen dargestellt.

Sternenkind
quelle
3

Es ist korrekt, aber nach 31 Iterationen berechnet 1073741824 + 1073741824 nicht richtig und gibt danach nur noch 0 aus.

Sie können die Verwendung von BigInteger umgestalten, damit Ihre Endlosschleife ordnungsgemäß funktioniert.

public class Mathz {
    static BigInteger i = new BigInteger("1");

    public static void main(String[] args) {    

        while (true){
            i = i.add(i);
            System.out.println(i);
        }
    }
}
Bruno Volpato
quelle
Wenn ich long anstelle von int verwende, scheint es lange Zeit zu sein, dass> 0 Zahlen gedruckt werden. Warum tritt dieses Problem nach 63 Iterationen nicht auf?
DeaIss
1
"Berechnet nicht richtig" ist eine falsche Charakterisierung. Die Berechnung ist korrekt gemäß der Java-Spezifikation. Das eigentliche Problem ist, dass das Ergebnis der (idealen) Berechnung nicht als dargestellt werden kann int.
Stephen C
@oOTesterOo - weil longkann größere Zahlen darstellen als intkann.
Stephen C
Long hat eine größere Reichweite. Der BigInteger-Typ akzeptiert alle Werte / Längen, die Ihre JVM zuweisen kann.
Bruno Volpato
Ich habe angenommen, dass int nach 31 Iterationen überläuft, weil es sich um eine maximale 32-Bit-Zahl handelt und so lange, wenn es sich um eine 64-Bit-Zahl handelt, nach 63 Iterationen die maximale Größe erreicht. Warum ist das nicht der Fall?
DeaIss
2

Zum Debuggen solcher Fälle empfiehlt es sich, die Anzahl der Iterationen in der Schleife zu reduzieren. Verwenden Sie dies anstelle von while(true):

for(int r = 0; r<100; r++)

Sie können dann sehen, dass es mit 2 beginnt und den Wert verdoppelt, bis es einen Überlauf verursacht.

user3732069
quelle
2

Ich werde zur Veranschaulichung eine 8-Bit-Zahl verwenden, da diese in kurzer Zeit vollständig detailliert werden kann. Hex-Zahlen beginnen mit 0x, während Binärzahlen mit 0b beginnen.

Der Maximalwert für eine 8-Bit-Ganzzahl ohne Vorzeichen beträgt 255 (0xFF oder 0b11111111). Wenn Sie 1 hinzufügen, erwarten Sie normalerweise: 256 (0x100 oder 0b100000000). Aber da das zu viele Bits (9) sind, ist das über dem Maximum, so dass der erste Teil einfach gelöscht wird und Sie effektiv 0 haben (0x (1) 00 oder 0b (1) 00000000, aber mit der 1).

Wenn Ihr Programm ausgeführt wird, erhalten Sie:

1 = 0x01 = 0b1
2 = 0x02 = 0b10
4 = 0x04 = 0b100
8 = 0x08 = 0b1000
16 = 0x10 = 0b10000
32 = 0x20 = 0b100000
64 = 0x40 = 0b1000000
128 = 0x80 = 0b10000000
256 = 0x00 = 0b00000000 (wraps to 0)
0 + 0 = 0 = 0x00 = 0b00000000
0 + 0 = 0 = 0x00 = 0b00000000
0 + 0 = 0 = 0x00 = 0b00000000
...
reiches remer
quelle
1

Das größte Dezimalliteral des Typs intist 2147483648 (= 2 31 ). Alle Dezimalliterale von 0 bis 2147483647 können überall dort erscheinen, wo ein int-Literal erscheinen kann, aber das Literal 2147483648 kann nur als Operand des unären Negationsoperators erscheinen -.

Wenn eine ganzzahlige Addition überläuft, sind das Ergebnis die niederwertigen Bits der mathematischen Summe, wie sie in einem ausreichend großen Zweierkomplementformat dargestellt werden. Wenn ein Überlauf auftritt, stimmt das Vorzeichen des Ergebnisses nicht mit dem Vorzeichen der mathematischen Summe der beiden Operandenwerte überein.

Scooba doo
quelle