Wider die Intuition

Inhaltsverzeichnis

Programmierer stoßen immer wieder auf Code, der zwar richtig aussieht, es aber leider nicht ist. Das hat zwar oft praktische Gründe, wird dadurch aber auch nicht besser.

Gerade beschäftige ich mich mit Gleitkommazahlen. Das ist ja schon an und für sich ein sehr interessantes Thema; aber es ist umso interessanter, weil beispielsweise in JavaScript die ganzen Zahlen auch in Form doppelt genauer Gleitkommazahlen (double) repräsentiert werden. Das Thema ist auch so sehr spannend und verdient es auch beizeiten an dieser Stelle diskutiert zu werden.

Bei der Behandlung dieser Gleitkommazahlen muss man gelegentlich das Bit-Muster manipulieren, hier und da ein Bit setzen oder löschen und einzelne Bits oder Bit-Gruppen durch die Gegend schieben. So auch bei der Umwandlung eines Strings in eine solche Zahl. Und bei dem Aufbau der Zahl ging dann nach einer vermeintlichen Vereinfachung leider immer etwas schief.

int high = … ;  // "obere" Hälfte
int low = … ;   // "untere" Hälfte
int k = … ;     // das hinzuzufügende Bit
if (k >= 32) {
    high |= 1 << (k - 32);
} else {
    low |= 1 << k;
}

Bei diesem Algorithmus wurde das double in zwei 32-Bit-Teile zerlegt und jeweils als int gespeichert. Um nun das k-te Bit zu setzen, isz zunächst zu entscheiden, ob dabei die obere (high) oder die untere Hälfte (low) betroffen ist. Dementsprechend wird der Index angepasst und das Bit in dem betroffenen Teil gesetzt.

Mit der breiten Verfügbarkeit von 64-Bit-Rechnern schien mir die Trennung in die beiden Einzelteile nicht mehr zeitgemäß. Also verzichtete ich auf diese Halbierung, um direkt mit dem 64-Bit-Wort zu arbeiten.

long mantissa = … ;  // die Mantisse des doubles
int k = … ;          // das hinzuzufügende Bit
mantissa |= 1 << k;

Leider funktionierte der Code nun nicht mehr. Eine Debug-Ausgabe brachte ans Licht, dass beispielsweise das Setzten des Bits k = 48 nun nicht mehr wie gewünscht

0x0001 0000 0000 0000

lieferte, sondern

0x0000 0000 0001 0000

Wo liegt der Fehler?

Um es gleich vorwegzunehmen: Der Fehler muss beim Shiften liegen. Aber warum?

Der Ausdruck 1 << k suggeriert, was er nicht leisten kann. Was vorher im Bereich 0 ≤ k < 32 problemlos funktionierte, geht jetzt schief, obwohl das betroffene mantissa ein long ist. Dazu muss man wissen, dass in vielen Programmiersprachen die höherwertigen Bits von k einfach ignoriert werden. Das führt – völlig überraschend – dazu, dass beim Shift für k = 48 nicht um die gewünschte Anzahl verschoben wird, sondern nur um k modulo 32, also nur um 16.

Dabei hilft auch nicht, dass das Ziel ein long ist. Der Compiler sieht nämlich nur, dass mit der 1 nur ein int verschoben wird, und nutzt deshalb dazu nur die niederwertigen 5 Bits. Erst nach dem Shift wird dann das int-Ergebnis in ein long konvertiert. Korrekt wäre also

mantissa |= 1L << k;

(wobei es besonders lustig ist, dass man auch das kleine L benutzen kann, um mit

mantissa |= 1l << k;

je nach eingesetztem Font größtmögliche Verwirrung stiften kann). Falsch machen kann man dann aber immer noch genug, denn das Shift eines longs berücksichtigt nur die niederwertigen 6 Bits.

Fehler der letzten Art gibt es mehrere. So liefert schon der banale Ausdruck, um die Nanosekunden für einen Tag zu berechnen,

long SECONDS_PER_DAY = 24 * 60 * 60 * 1000 * 1000;

nicht wie gewünscht 86.400.000.000, sondern nur 500.654.080. Das ist ein Fehler, der erst entdeckt werden will. Will man die Nanosekunden für ein ganzes Jahres berechnen, erhält man wenigstens mit −1.944.854.528 ein negatives Ergebnis, was ja sicherlich nicht sein kann. Und dabei hilft es eben nicht, dass das Ergebnis in einem long abgelegt werden soll, das locker Platz für das korrekte Ergebnis gehabt hätte. Im Gegensatz zum Java-Compiler ist der C#-Compiler wenigstens so freundlich und teilt bei Konstanten einem den Überlauf schon zur Übersetzungszeit mit.

Mein Fehler oben hätte sofort und ohne großartige Suche entdeckt werden können, wenn ich zumindest über den "Überlauf" informiert worden wäre. Klammheimlich Bits unbeachtet zu lassen scheint mir da nicht die korrekte Methode zu sein.

Unterschiedliches Verfahren

An dieser Stelle sei aber noch erwähnt, dass in meinem Fall eine Überlauf-Ausnahme zwar sofort geholfen hätte, aber dennoch viele subtile Fehler lange Zeit unentdeckt bleiben können. So steht in dem berühmten Buch "Programming Pearls" [1] ein nachweislich korrekter Algorithmus für die binäre Suche, der leider einen Fehler enthält, weil er den Mittelwert m zweier Zahlen l und u mit

m = (l + u) / 2

berechnet. Dieser nicht intuitive Fehler – die so berechnete Hälfte wird bei großem l und u schon mal negativ – blieb über 20 Jahre unentdeckt, weil bis Mai 2004 wohl niemand ein Element in einem Array binär gesucht hat, das mehr als 2³⁰ Elemente enthielt. Dank Java gab es dann aber wenigstens eine Ausnahme, die leicht auf den Fehler schließen ließ. Eine Implementierung in einer nicht so restriktiven, sicheren Sprache wie C hätte im schlimmsten Fall einfach irgendwelche Hausnummern geliefert, was möglicherweise zu völlig anderen Schlüssen (wie fehlerhafte Daten oder fehlerhafter Algorithmus) geführt hätte. (Eine ausführliche, vergnüglichere Beschreibung dieses Problems findet sich übrigens im KaffeeKlatsch [2].)

Bezüglich der Überläufe macht es Swift konsequent richtig, weil dort immer auf Überläufe geprüft wird, während man in C# immerhin die sichere Berechnung explizit nutzen kann. Aber wer macht so etwas schon freiwillig, wenn es auch ohne geht!?

Schön wäre jetzt noch, wenn Programmiersprachen das Ziel einer Berechnung mit in die Entscheidung einbeziehen würden, damit diese subtilen Fehler weitestgehend eliminiert werden.

Referenzen

1. Jon Bentley; Programming Pearls; ACM Press 1986
2. Michael Wiedeking; Des Programmierers kleine Vergnügen – über die Halbsumme zweier ganzer Zahlen; KaffeeKlatsch, Jahrgang 1, Nr. 1, S. 29f, Bookware, Januar 2008

()