Geteiltes Leid: Von der Division in Programmiersprachen

Zu den interessantesten Dingen in der Informatik gehört sicherlich die Division. Vielleicht verführt aber der Umstand, dass es die allerlahmste Operation ist, dazu, im Zusammenhang mit Zweierpotenzen auf das Shiften zurückzugreifen – was allerdings nicht immer zum gewünschten Ergebnis führt.

Als die Programmiersprache Swift veröffentlicht wurde, war auch ich sehr gespannt darauf, wie sich eine Sprache aus dem Hause Apple wohl anfügen mag. So habe ich mir die "Spezifikation" heruntergeladen und abends vor dem Zubettgehen zu Gemüte geführt. Ich war sehr angetan, war sie doch durchdacht und auf die Bedürfnisse der Apple-Entwickler angepasst – neu und modern, aber ohne die Herkunft zu verleugnen.

Neben der Syntax spielt es noch eine Rolle, was die Sprache denn alles mitbringt. So interessiert mich immer, was neben den Basisoperationen sonst noch zu haben ist. Im letzten Kapitel "Advanced Operators" endlich bin ich fündig geworden, wie man die Maschinenwörter manipulieren kann. Und da stand dann:

"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."

Daraufhin habe ich mir sofort die aktuelle Version von Xcode herunterladen wollen, was aber damals nicht ging, weil man dazu wegen des Beta-Status der Entwicklungsumgebung erst noch Mitglied im Apple-Entwicklerprogramm werden musste. Ich erinnere mich noch, dass ich gefühlte Ewigkeiten warten musste, bis die Mitgliedschaft bestätigt wurde. Dann hat es Stunden gedauert, bis das ganze Geraffel endlich geladen war. Endlich konnte ich das Versprochene ausprobieren – und wurde bitterlich enttäuscht.

Ich weiß ja nicht, warum es immer wieder Aussagen gibt, die sich so hartnäckig halten, obwohl immer und immer wieder gezeigt oder gar nachgewiesen wird, dass diese nicht stimmen. Im Zusammenhang mit den Programmiersprachen scheint das die Dualität von der Division mit Zweierpotenzen und dem Shiften zu sein.

Will man wissen, wie oft die 8 in die 19 passt, bedient man sich der ganzzahligen Division:

19 / 8 = 2.

Da es sich bei der 8 um eine Zweierpotenz, nämlich 2³, handelt, kann die Division auch durch einen Rechts-Shift >> ersetzt werden:

19 >> 3 = 2.

Wenn man nun noch wissen will, wie oft die 8 in –19 passt, so sagt Swift (und die meisten anderen Programmiersprachen auch):

-19 / 8 = –2.

Super, und jetzt wie versprochen die Division durch ein Shift ersetzen:

-19 >> 3 = –3.

Oha! Das ist nicht ganz das, was man nach obiger Aussage erwarten würde.

Umgang mit negativen Zahlen

Negative Zahlen werden ja ein wenig überbewertet, weswegen viele Applikationen ganz ohne auskommen. Wie oben zu sehen ist, gibt es dann auch keine Probleme. Im Zusammenhang mit negativen Zahlen sieht die Welt allerdings nicht so rosig aus. Und dazu braucht man noch nicht einmal ein Shift.

Die Division, wie sie bei den meisten Prozessoren und bei vielen Programmiersprachen definiert ist, schneidet den nicht ganzzahligen Anteil einfach ab. Das heißt: 19 / 8 = 2,375, abgeschnitten 2; analog –19 / 8 = –2,375, abgeschnitten 2. Das mag brauchbar erscheinen, ist es aber nicht.

Will man etwa wissen, in welchen Vierer-Karton man nummerierte Bälle stecken muss, damit man sie leicht wiederfindet, dividiert man deren Nummer einfach durch 4 und erhält so die Nummer der Kiste. Ball 0 landet in der Kiste 0 / 4 = 0, Ball 1 in der Kiste 1 / 4 = 0, und die Bälle 2 und 3 landen wegen 2 / 4 = 3 / 4 = 0 ebenfalls dort. Der Ball 4 muss aber schon in die Kiste 4 / 4 = 1 usw. Leider haben wir auch mit negativen Zahlen beschriftete Bälle. Und deshalb landet Ball –1 in der Kiste … wait for it … –1 / 4 = 0, die aber leider schon voll ist.

Dieses nichtkontinuierliche Verhalten ist nicht intuitiv. Über die dazugehörigen Reste-Funktionen lassen sich vergleichbare Aussagen machen. Insgesamt gibt es (mindestens) vier relevante Möglichkeiten zu einem ganzzahligen Divisionsergebnis zu kommen:

• Runden gegen –unendlich,
• Runden gegen +unendlich,
• Runden zur nächsten Zahl

und ganz zum Schluss erst Abschneiden.

Hier macht es beispielsweise Python richtig, das sich (anscheinend aber auch nicht von Anfang an) bei der ganzzahligen Standarddivision für das Runden gegen –unendlich entschieden hat, welches mit dem Rundungsverhalten der Shifts bei Zweierpotenzen übereinstimmt.

Fazit

Zusammenfassen bleibt demnach nur noch zu sagen: Weil beim vorzeichenbehafteten Shiften nach rechts gegen –unendlich gerundet wird, muss man sehr sorgfältig darauf achten, wie die ganzzahlige Division rundet, um sicher zu gehen, dass das eine gegen das andere ausgetauscht werden darf, insbesondere wenn auch negative Zahlen im Spiel sind. ()