Das folgende C++-Programm kann Ihnen zeigen, wie ein Überlauf bei einer 32-Bit-Ganzzahl ohne Vorzeichen entstehen kann:
#include <iostream>
using namespace std;
int main ()
{
unsigned int low = 33,
high = 4294967290,
mid;
cout << "The value of low is " << low << endl;
cout << "The value of high is " << high << endl;
mid = (low + high) / 2;
cout << "The value of mid is " << mid << endl;
return 0;
}
Wenn Sie es auf einem Mac ausführen:
$ g++ try.cpp && ./a.out
The value of low is 33
The value of high is 4294967290
The value of mid is 13
Der Wert von mid könnte man erwarten, dass 2147483661 aber low + high überlaufen, weil eine 32-Bit-Ganzzahl ohne Vorzeichen nicht den richtigen Wert enthalten kann, und geben zurück 27 , und so mid wird 13 .
Wenn die Berechnung von mid wird geändert in
mid = low + (high - low) / 2;
Dann wird angezeigt
The value of mid is 2147483661
Die einfache Antwort ist, dass der Zusatz l + u kann überlaufen und hat in einigen Sprachen ein undefiniertes Verhalten, wie in ein Blogbeitrag von Joshua Bloch über einen Fehler in der Java-Bibliothek für die Implementierung der Binärsuche .
Einige Leser verstehen vielleicht nicht, worum es geht:
l + (u - l) / 2
Beachten Sie, dass in einigen Codes die Variablennamen anders lauten, und es ist
low + (high - low) / 2
Die Antwort ist: Sagen wir, Sie haben zwei Zahlen: 200 und 210, und du willst nun die "mittlere Zahl". Und wenn Sie zwei Zahlen addieren und das Ergebnis größer als 255 ist, kann es zu einem Überlauf kommen und das Verhalten ist undefiniert, was können Sie dann tun? Eine einfache Möglichkeit besteht darin, die Differenz zwischen den beiden Zahlen, aber nur die Hälfte davon, zum kleineren Wert zu addieren: Schauen Sie sich an, was die Differenz zwischen 200 und 210 ist. Sie beträgt 10. (Man kann sie als "Differenz" oder "Länge" zwischen den beiden Werten betrachten). Sie müssen also nur Folgendes addieren 10 / 2 = 5 auf 200 und erhalten 205. Man muss nicht erst 200 und 210 zusammenzählen - und so kommen wir zur Berechnung: (u - l) ist der Unterschied. (u - l) / 2 ist die Hälfte davon. Addieren Sie das zu l und wir haben l + (u - l) / 2 .
Wenn wir zwei Bäume betrachten, von denen einer 200 Fuß hoch ist und der andere 210 Fuß hoch, was ist dann der "Mittelpunkt" oder der "Mittelwert"? Wir müssen sie nicht erst zusammenzählen. Wir können einfach sagen, dass der Unterschied 10 Fuß beträgt, und wir können die Hälfte davon, also 5, zu 200 addieren, und wir wissen, dass es 205 Fuß sind.
Um dies in eine historische Perspektive zu rücken, erwähnte Robert Sedgewick, dass die erste binäre Suche im Jahr 1946 angegeben wurde und erst 1964 korrekt war. Jon Bentley beschrieb 1988 in seinem Buch Programming Pearls, dass mehr als 90 % der professionellen Programmierer sie in ein paar Stunden nicht korrekt schreiben könnten. Aber sogar Jon Bentley selbst hatte diesen Überlauffehler 20 Jahre lang. Eine 1988 veröffentlichte Studie zeigte, dass nur in 5 von 20 Lehrbüchern korrekter Code für die Binärsuche zu finden war. Im Jahr 2006 schrieb Joshua Bloch diesen Blogbeitrag über den Fehler bei der Berechnung der mid Wert. Es hat also 60 Jahre gedauert, bis dieser Code korrekt war. Aber denken Sie beim nächsten Vorstellungsgespräch daran, dass Sie den Code in diesen 5 Minuten richtig schreiben müssen.
