Division und Multiplikation mit Verschiebeoperatoren

Wird ein Wert um eine Stelle nach links geschoben, so kommt in das niedrigste Bit (das Bit ganz rechts) eine Null, und alle Bits verschieben sich um eine Stelle weiter. Das Resultat: Die Zahl wird mit 2 multipliziert. Natürlich müssen wir mit einem Verlust von Informationen rechnen, wenn das höchste Bit gesetzt ist, denn dann wird es herausgeschoben, aber das Problem haben wir auch schon bei der normalen Multiplikation. Es gibt in Java keinen Operator, der die Bits rollt, der also die an einer Stelle herausfallenden Bits an der anderen Seite wieder einfügt.

Da eine einmalige Verschiebung nach links mit 2 multipliziert, bewirkt eine Verschiebung um zwei Stellen nach links eine Multiplikation mit 4. Allgemein gilt: Bei einer Linksverschiebung um i Positionen ergibt sich eine Multiplikation mit 2^i. Wir können dies dazu nutzen, beliebige Multiplikationen durch Verschiebung nachzubilden.

Beispiel: Multiplikation mit 10 durch Verschiebung der Bit:

10 * n == n << 3 + n << 1

Das funktioniert, da 10*n = (8+2)*n = 8*n + 2*n gilt.

Diese Umsetzung ist nicht immer einfach, und es gibt tatsächlich kein Verfahren, das eine optimale Umsetzung liefert. Doch arbeiten viele Prozessoren auf diese Weise intern die Multiplikation ab, und ein Compiler nutzt dies gern zur Optimierung der Laufzeit. Eine Verschiebeoperation ist bei vielen Prozessoren schneller als eine Multiplikation. Doch ist hier Obacht zu geben, denn eine lange Folge von Verschiebungen ist nicht schneller, sondern langsamer als eine direkte Multiplikation.

Neben der Addition kommt selbstverständlich auch die Subtraktion infrage. Ersetzen wir im oberen Beispiel das Plus durch ein Minus, so bekämen wir eine Multiplikation mit 6. Natürlich müssen wir auf die Überläufe der Zwischenergebnisse bei großen Zahlen achten. Diese würde es bei einer echten Multiplikation nicht geben.

Was wir am Beispiel der Verschiebung nach links gezeigt haben, funktioniert genauso mit einer Rechtsverschiebung. Jetzt dividiert die einmalige Verschiebung durch 2. Das Ergebnis ist natürlich immer nur ganzzahlig, da die Verschiebeoperatoren nur auf int und long definiert sind; so ist 7 >> 2 = 3. Bei negativen Zahlen sieht das etwas anders aus, denn hier ist das Ergebnis –7 >> 2 = –4. Würden wir die Division ganz klassisch mit / 2 realisieren, ist das Ergebnis 7 / 2 = 3 und –7 / 2 = –3. Bei einer gedachten Optimierung ist auf diese Besonderheit bei negativen Zahlen zu achten.