Leidvolle (Mit-)Teilung

Inhaltsverzeichnis

Geteiltes Leid ist halbes Leid. Wer's glaubt. Hat man sich nämlich mitgeteilt und wird nicht verstanden, dann wird das Leid leider nur aufgeschoben, bis durch eine negative Zahl geteilt werden muss.

Da dachte ich, dass es sich lohnen könnte, meine Begeisterung für die Hoffnung auf eine "vernünftige" Division mit der Welt zu teilen; aber weit gefehlt: Anscheinend habe ich mich beim letzten Blog-Beitrag nicht klar genug ausgedrückt. Deshalb versuche ich es hier einfach noch einmal.

Der Ausgangspunkt

Grundlage für den letzten Blog-Eintrag war die in dem Kapitel "Advanced Operators" der Swift-"Spezifikation" getätigte Aussage

"Bitwise left and right shifts have the effect of multiplying or dividing an integer by a factor of two. Shifting an integer’s bits to the left by one position doubles its value, whereas shifting it to the right by one position halves its value."

Wenn es eine Shift-Operation x >> k gibt, die unter Berücksichtigung des Vorzeichens ein Verschieben der Bits in x nach "rechts" um k Stellen möglich macht, dann funktioniert diese Operation wie eine nach –∞ gerundete Division von x durch die zu k gehörige Zweierpotenz, vorausgesetzt dass x und k ganzzahlig sind und k ≥ 0 ist.

x >> k = ⌊x / 2k⌋

Dabei liefert der Floor-Operator ⌊x⌋ die größte ganze Zahl, die kleiner oder gleich x ist (und rundet demnach die gegebene Zahl gegen –∞).

Gibt es darüber hinaus noch eine Shift-Operation x << k, dann funktioniert diese analog wie eine Multiplikation von x mit der zu k gehörenden Zweierpotenz.

x << k = x · 2k

Der für das Problem irrelevante Exkurs

Dabei stellt sich mir zunächst einmal nicht die Frage, ob und wie k ausgewertet wird. Bezogen auf obige Aussage kann aber k (möglicherweise in Abhängigkeit von x) nicht beliebig groß sein, da sonst die angepriesene Dualität nicht haltbar wäre. Bei einem 32-Bit-Wort wäre dann also vernünftigerweise k auf 31 beschränkt, da 2^k ja sonst nicht mehr darstellbar wäre. Allgemein kann man also davon ausgehen, dass bei einem k-Bit-Wort bis zu k – 1 Stellen geschoben werden könnte.

Natürlich müssen sich Programmiersprachen-Designer dann noch Gedanken darüber machen, was passieren soll, wenn mit dem Schieben das Vorzeichen geändert oder der Wertebereich überschritten wird, es also zu einem Überlauf kommt. Aber das ist ein anderes (ebenso kontrovers diskutiertes) Thema. Beim Shiften nach "links" könnte demnach ein Überlauf mit einer Ausnahme oder gar mit einem Programmabbruch quittiert werden; dabei mag es zu einer Null führen, wenn alle gesetzten Bits herausgeschoben wurden; eine positive Zahl kann negativ werden, wenn durch das Verschieben das Vorzeichen-Bit gesetzt wird – und umgekehrt positiv werden, wenn jenes gelöscht wird. Und schließlich können nur Teile von k zum Schieben genutzt werden, wie bereits im Blog-Beitrag "Wider die Intuition" geschildert wurde.

Nebenbei bemerkt macht der zitierte Abschnitt der Swift-"Spezifikation" darüber, inwieweit k bezüglich der Shift-Operation ausgewertet wird, leider gar keine Aussagen. Auch das muss man also (wie in vielen Sprachen wegen der mangelhaften Dokumentation) mühsam ausprobieren. Das Programm wird analog zu den "Überläufern" abgebrochen, wenn k bezogen auf die Breite von x zu groß ist; ob durch das Shiften der Wertebereich der Variablen überschritten wird, ist dabei irrelevant. Letzteres macht nicht nur einen weiteren Unterschied zur Multiplikation aus, sondern verwässert auch noch das Überlaufverhalten. Denn bezogen auf die Dualität müsste 0 << 1000 durchaus zulässig sein, während (1 << 63) << 1 zu einem Überlauf führen müsste, aber dennoch erlaubt ist und 0 ergibt (die Konstanten werden hier in Swift als vorzeichenlose 64-Bit-Zahl interpretiert).

Aber eigentlich hat das gar nichts mit dem geschilderten Problem zu tun.

Die Krux mit der Division

Im letzten Blog-Beitrag wurde die Existenz einer solchen Shift-Operation im Zusammenhang mit Swift als gegeben vorausgesetzt. Die eigentlich nur wegen des Zitats angegebene Referenz enthält auch entsprechende Erläuterungen, insbesondere was ein Rechts-Shift bezüglich des Vorzeichen-Bits anbetrifft. Nebenbei bemerkt sind in diesem Zusammenhang Sprachen, die kein vorzeichenbehaftetes Shiften anbieten, uninteressant. Die machen dann in der Regel aber auch keine Aussagen über die Dualität von vorzeichenbehaftetem Shiften und der dazugehörigen Division. Und im vorzeichenlosen Fall ist obige Aussage ja korrekt.

Das Shiften liefert etwa bei der Division durch 2 (was ja 2^1 ist) bei positiven Zahlen die nach unten gerundete Hälfte: 4 >> 1 = 2, 3 >> 1 = 1, 2 >> 1 = 1, 1 >> 1 = 0, 0 >> 1 = 0. Bei negativen Zahlen wird dann aber auch nach unten gerundet: –4 >> 1 = –2, –3 >> 1 = –2, –2 >> 1 = –1, –1 >> 1 = –1. Das bedeutet insbesondere, dass es auch bei der Division mit Rundung gegen –∞ keinen Bruch hinter der Null gibt:

…, ⌊–3/2⌋ = –2, ⌊–2/2⌋ = –1, ⌊–1/2⌋ = –1, ⌊0/2⌋ = 0, ⌊1/2⌋ = 0, ⌊2/2⌋ = 1, ⌊3/2⌋ = 1, …

Im Gegensatz dazu definieren viele Programmiersprachen die ganzzahlige Division derart, dass sie einfach den nicht ganzzahligen Teil abschneiden. Stellt man das nun durch × dar, erhält man leider an der Stelle um die 0 ein unerwünscht seltsames Verhalten:

…, [–3/2] = –1, [–2/2] = –1, [–1/2] = 0, [0/2] = 0, [1/2] = 0, [2/2] = 1, [3/2] = 1, …

Diese Störung ist so unangenehm, dass ich diejenige Art der Division, die durch das kontinuierliche Runden gegen –∞ erreicht wird, grundsätzlich bevorzuge.

Der Übersicht halber werden die Ergebnisse obiger Quotienten und einiger mehr nochmals gegenübergestellt (wobei 0/2 fett dargestellt wird):

–4 –4 –3 –3 –2 –2 –1 –1  0  0  1  1  2  2  3  3  4  4
–4 –3 –3 –2 –2 –1 –1  0  0  0  1  1  2  2  3  3  4  4

Warum die zweite Zeile so problematisch ist, sollte dann doch das Beispiel in der letzten Kolumne gezeigt haben.

Die zerstörte Hoffnung

Vielleicht hätte ich meine Erwartungen nicht ganz so hoch schrauben sollen. Da das Verhalten von vorzeichenbehaftetem Shiften eindeutig ist und sicherstellt, dass bei vergleichbarer Division gegen –∞ gerundet wird, habe ich mich so über die Aussage in der Swift-"Spezifikation" gefreut. Aber aus Erfahrung klug geworden, habe ich mich nicht darauf verlassen und ausprobiert, ob das Shiften wirklich wie die Division bzw. die Multiplikation mit der entsprechenden Zweierpotenz funktioniert.

Aus der eingangs geschilderten Aussage nun das von mir gewünschte Idealverhalten abzuleiten, war wohl etwas vermessen. Es ist schade, dass auch wider besseren Wissens immer noch nur die eine Divison zur Verfügung steht, die den Hardware-Entwicklern die Arbeit vor mehr als einem halben Jahrhundert leichter gemacht hat. Wer übrigens glaubt, dass es einfach ist, auf Basis der abschneidenden Division die "vernünftige" zu implementieren, der kann ja mal versuchen, das in nur einem Wurf zu schaffen – idealerweise ohne Bedingung.

Das Fazit

Aus dem letzten und nun auch diesem Blog-Eintrag sollten Leser also zwei Dinge mitnehmen:

1. Die Dualität von Multiplikation/Division und Links-/Rechts-Shift ist dann – und nur dann – gegeben, wenn bei der Division gegen –∞ gerundet wird (und 2^k bzw. k vernünftige Werte haben). Wenn man also einen solchen Satz in einer Spezifikation liest, ist das nur allzu oft wie die Mär vom Vogel Strauß, der den Kopf in den Sand steckt, und man sollte sorgfältig prüfen, ob und in welchem Umfang diese Aussage stimmt.
2. Die ganzzahlige Division, bei der das Ergebnis gegen –∞ gerundet wird, hat um die 0 ein kontinuierlicheres Verhalten, das eine Gruppe von subtilen Fehlern ausschließt. Dann – und nur dann – kann man diese Division dazu brauchen, nützliche Divisionen mit anderem Rundungsverhalten zu implementieren, was mit der den Rest abschneidenden Division nicht ohne Fallunterscheidung für die negativen Zahlen funktioniert.

Dass die Division eine nicht triviale Angelegenheit ist, zeigen viele Beispiele aus anderen Sprachen, die oft mit dem zugrunde liegenden System zusammenhängen. Das Runden gegen 0 hat etwa mit dem Intel-Prozessor zu tun. Oder die Division durch 0, die bei vielen Sprachen zu einer Ausnahme führt, aber bei Sprachen, deren ganzzahligen Operationen auf Fließkommazahlen abgebildet werden (wie etwa JavaScript) liefert Infinity und bei dem mathematisch nicht definierten 0/0 den Wert NaN.

Das im letzten Beitrag erwähnte Python hat wohl schon immer die Division "richtig" (also mit dem runden gegen –∞) berechnet. Dort hatte man aber das Problem, dass das Operator-Symbol / sowohl für ganze als auch komplexe, rationale oder Gleitkommzahlen verwendet werden kann. Das führte aber bis Python 2 dazu, dass 3 / 2 = 1 aber 3.0 / 2 = 1.5 ist. Da man in Python dynamisch typisierte Funktionen schreiben kann, kamen also "zufällig" bei gleicher Funktion unterschiedliche Ergebnisse heraus. Deshalb gibt es seit Python 3 zwei Operatoren: der für die normale Divison 3 / 2 = 1.5 und den für die ganzzahlige Division 3 // 2 = 1.

Also alles nicht ganz so einfach.

Notabene

Übrigens soll der Umstand, dass man explizit Shiften und damit eine Division ersetzen kann, nicht unbedingt dazu verleiten, das auch tatsächlich zu tun. Wer etwa eine Wert halbieren möchte, macht das besser klar, in dem er etwa x/2 schreibt. Das Shiften ist also tendenziell nur denjenigen vorbehalten, die wirklich Bits verschieben wollen – oder die durch eine variable Zweierpotenz teilen bzw. damit multiplizieren wollen.

Der Shift-Operator muss im letzten Fall tatsächlich als spezialisierte Funktionen

multiplyWithPowerOfTwo(x, k)
divideByPowerOfTwo(x, k)

mit variablem k verstanden werden. Würde man nämlich auf den Shift-Operator verzichten wollen, so müsste man ja statt x >> k etwa

x / ipow(2, k)

schreiben. In Anbetracht dessen, dass viele Programmiersprachen gar keine ganzzahlige Potenzfunktion anbieten, müsste eine solche Funktion also erst noch geschrieben werden – und da sagt die Erfahrung, dass die meisten Entwickler nur einen Algorithmus mit Komplexität O(n) statt des deutlich besseren O(log n) – oder in diesem speziellen Fall sogar O(1) – implementieren würden. Das Shiften hat also durchaus auch bei den modernen Prozessoren seine Existenzberechtigung.

Postskriptum

Dem "Runden gegen –∞" wird im normalen Sprachgebrauch durchaus mit "abrunden" Ausdruck verliehen. Allerdings darf es einen nicht verwundern, wenn "abrunden" insbesondere bei negativen Zahlen dann auch schon mal fälschlich als das betragsmäßige Abrunden, also das Abrunden gegen 0 verstanden wird. Das liegt unter anderem daran, dass "abrunden" keine eindeutige Richtung beinhaltet. So sagt etwa der Duden (6. Aufl. Mannheim 2006) zu abrunden

"eine Zahl [nach unten, seltener oben] abrunden"

oder auch genauer

"eine Zahl durch Abziehen od. Hinzufügen auf die nächste runde Zahl bringen: 81,5 auf 81 od. 82 a.; eine Summe a. (häufiger: durch Abziehen auf die nächste runde Zahl bringen)."

Nur bei aufrunden ist sich der Duden darüber einig, dass dies nach oben ist. Damit gibt nur das Runden gegen –∞ für alle Zahlen eineindeutig an, in welche Richtung gerundet wird. ()