Für welchen Wert von i wird while (i == i + 1) {} für immer wiederholt?

120

Ich habe dieses Rätsel bei einem fortgeschrittenen Programmierkurs bei einer britischen Universitätsprüfung gekreuzt .

Betrachten Sie die folgende Schleife, in der i bisher nicht deklariert ist:

while (i == i + 1) {}

Suchen Sie die Definition von i, die dieser Schleife vorausgeht, sodass die while-Schleife für immer fortgesetzt wird.

Die nächste Frage, die dieselbe Frage für dieses Code-Snippet stellte:

while (i != i) {}

war mir klar. Natürlich ist es in dieser anderen Situation so, NaNaber ich stecke wirklich in der vorherigen fest. Hat das mit Überlauf zu tun? Was würde dazu führen, dass eine solche Schleife in Java für immer wiederholt wird?

java loops types jake mckenzie
quelle
3
Gibt es Möglichkeiten, die .equals()Methode zu überschreiben ? Da ich nicht deklariert bin, können wir jede Klasse von dem verwenden, was wir wollen.
Geno Chen
7
@ Raedwald studiert "unprofessionellen" Code macht Sie "professioneller", also ... Wie auch immer, es ist eine gute Frage
Andrew Tobilko
12
Unterhaltsame Tatsache, dass dies in C # auch für nullfähige numerische Typen funktioniert, deren Werte sind null, da dies null == nullwahr ist und null + 1ist null.
Eric Lippert
4
@ EricDuminil: Die Situation ist weitaus schlimmer als Sie sich vorstellen. In vielen Sprachen muss die Gleitkomma-Arithmetik mit mindestens 64 Bit Genauigkeit durchgeführt werden, was durch ein Double angegeben wird. Dies bedeutet, dass sie nach Lust und Laune des Compilers mit höherer Genauigkeit ausgeführt werden kann. In der Praxis geschieht dies . Ich kann Sie auf ein Dutzend Fragen von C # -Programmierern auf dieser Site verweisen, die sich fragen, warum 0.2 + 0.1 == 0.3sich der Wert abhängig von den Compilereinstellungen, der Mondphase usw. ändert.
Eric Lippert
5
@EricDuminil: Die Schuld für dieses Durcheinander liegt bei Intel, der uns einen Chipsatz gegeben hat, der eine präzisere und schnellere Gleitkomma-Arithmetik ausführt, wenn die Zahlen registriert werden können, was bedeutet, dass die Ergebnisse einer Gleitkomma-Berechnung ihre Werte abhängig ändern können wie gut der Register Scheduler im Optimierer heute funktioniert. Als Sprachdesigner haben Sie dann die Wahl zwischen wiederholbaren Berechnungen und schnellen, präzisen Berechnungen . Die Community, die sich für Gleitkomma-Mathematik interessiert, wird sich für Letzteres entscheiden.
Eric Lippert

Antworten:

142

Da die while (i == i + 1) {}Schleife den Wert von nicht ändert i, ist es zunächst äquivalent, diese Schleife unendlich zu machen, um einen Wert zu wählen i, der erfüllt i == i + 1.

Es gibt viele solche Werte:

Beginnen wir mit den "exotischen":

double i = Double.POSITIVE_INFINITY;

oder

double i =  Double.NEGATIVE_INFINITY;

Der Grund für die Erfüllung dieser Werte i == i + 1ist in
JLS 15.18.2 angegeben. Additive Operatoren (+ und -) für numerische Typen :

Die Summe einer Unendlichkeit und eines endlichen Wertes ist gleich dem unendlichen Operanden.

Dies ist nicht überraschend, da das Hinzufügen eines endlichen Wertes zu einem unendlichen Wert zu einem unendlichen Wert führen sollte.

Das heißt, die meisten Werte i, die erfüllen, i == i + 1sind einfach große double(oder float) Werte:

Beispielsweise:

double i = Double.MAX_VALUE;

oder

double i = 1000000000000000000.0;

oder

float i = 1000000000000000000.0f;

Die doubleund float-Typen haben eine begrenzte Genauigkeit. Wenn Sie also einen ausreichend großen Wert doubleoder floatWert verwenden, führt das Hinzufügen 1zu demselben Wert.

Eran
quelle
10
Oder (double)(1L<<53)- oderfloat i = (float)(1<<24)
dave_thompson_085
3
@ Ruslan: Jeder Mathematiker würde nicht zustimmen. Gleitkommazahlen machen wenig Sinn. Sie sind nicht assoziativ, nicht reflexiv (NaN! = NaN) und nicht einmal substituierbar (-0 == 0, aber 1/0! = 1 / -0). Daher ist der größte Teil der Maschinerie der Algebra nicht anwendbar.
Kevin
2
@ Kevin Während Gleitkommazahlen im Allgemeinen nicht allzu viel Sinn machen können, wurde das Verhalten von Unendlichkeiten (wie in diesem Satz beschrieben) so konzipiert, dass es Sinn macht.
Ruslan
4
@ Kevin Um fair zu schweben, wenn Sie mit Unendlichkeiten oder undefinierten Werten arbeiten, können Sie auch nicht die Eigenschaften annehmen, die Sie in der Algebra aufgelistet haben.
Voo
2
@ Kevin: IMHO, Gleitkomma-Mathematik hätte viel sinnvoller sein können, wenn sie die Konzepte des positiven, negativen und vorzeichenlosen "Infinitesimals" mit einer "wahren Null" ersetzt und gemacht hätte NaN gleich sich selbst. Die wahre Null könnte sich in allen Fällen als additive Identität verhalten , und Operationen, die die Division durch Infinitesimale beinhalten, würden ihre Neigung verlieren, anzunehmen, dass die Infinitesimale positiv sind.
Supercat
64

Diese Rätsel werden ausführlich im Buch "Java Puzzlers: Fallen, Fallstricke und Eckfälle" von Joshua Bloch und Neal Gafter beschrieben.

double i = Double.POSITIVE_INFINITY;
while (i == i + 1) {}

oder:

double i = 1.0e40;
while (i == i + 1) {}

Beides führt zu einer Endlosschleife, da durch Hinzufügen 1zu einem ausreichend großen Gleitkommawert der Wert nicht geändert wird, da die Lücke zu seinem Nachfolger 1 nicht "überbrückt" wird .

Ein Hinweis zum zweiten Puzzle (für zukünftige Leser):

double i = Double.NaN;
while (i != i) {}

führt auch zu einer Endlosschleife, da NaN keinem Gleitkommawert entspricht, einschließlich sich selbst 2 .

1 - Java-Puzzler: Fallen, Fallstricke und Eckfälle (Kapitel 4 - Loopy-Puzzler).

2 - JLS §15.21.1

Oleksandr Pyrohov
quelle
1

double i = Double.POSITIVE_INFINITY;

Farcas George
quelle
0

Nur eine Idee: Was ist mit Booleschen?

bool i = TRUE;

Ist das nicht ein Fall wo i + 1 == i?

Dominique
quelle
hängt von der Sprache ab. Viele Sprachen zwingen Boolesche Werte automatisch zu Ints, wenn sie mit einem Int kombiniert werden. Andere tun, was Sie vorschlagen - zwingen das int zu einem Booleschen Wert.
Carl Witthoft
8
Diese Frage ist eine Java-Frage, und Ihr Vorschlag besteht keine Kompilierung in Java (das keinen +Operator hat, der a booleanund a intals Operanden verwendet).
Eran
@Eran: Das ist die ganze Idee der Operatorüberladung. Sie können dafür sorgen, dass sich Java-Boolesche Werte wie C ++ verhalten.
Dominique
4
Abgesehen davon, dass Java das Überladen von Operatoren nicht unterstützt, können Sie dies nicht.
CupawnTae