Bitweise Operation

Die Bitverschiebungen werden manchmal auch als bitweise Operationen bezeichnet, da sie einen Wert als eine Reihe von Bits und nicht als eine numerische Größe behandeln. Bei diesen Operationen werden die Ziffern nach links oder rechts verschoben, also geshiftet. Register in einem Computerprozessor haben eine feste Breite, so dass einige Bits an einem Ende aus dem Register „herausgeschoben“ werden, während die gleiche Anzahl von Bits vom anderen Ende „hineingeschoben“ wird; die Unterschiede zwischen Bit-Schiebe-Operatoren liegen darin, wie sie die Werte der hineingeschobenen Bits bestimmen.

Bitadressierung

Ist die Breite des Registers (häufig 32 oder sogar 64) größer als die Anzahl der Bits (meist 8) der kleinsten adressierbaren Einheit (atomares Element), häufig Byte genannt, so bewirken die Schiebeoperationen ein Adressierungsschema auf den Bits.Vernachlässigt man die Randeffekte an beiden Enden des Registers, so verhalten sich arithmetische und logische Schiebeoperationen gleich, und eine Verschiebung um 8 Bitpositionen transportiert das Bitmuster um 1 Byteposition auf folgende Weise:

Arithmetische Verschiebung

Linke arithmetische Verschiebung

Rechte arithmetische Verschiebung

Bei einer arithmetischen Verschiebung, werden die Bits verworfen, die aus einem der beiden Enden herausgeschoben werden. Bei einer arithmetischen Linksverschiebung werden rechts Nullen eingeschoben, bei einer arithmetischen Rechtsverschiebung wird das Vorzeichenbit (das MSB im Zweierkomplement) links eingeschoben, wodurch das Vorzeichen des Operanden erhalten bleibt.

In diesem Beispiel wird ein 8-Bit-Register verwendet, das als Zweierkomplement interpretiert wird:

 00010111 (decimal +23) LEFT-SHIFT= 00101110 (decimal +46)

 10010111 (decimal −105) RIGHT-SHIFT= 11001011 (decimal −53)

Im ersten Fall wurde die äußerste linke Ziffer am Ende des Registers vorbeigeschoben, und eine neue 0 wurde in die äußerste rechte Position geschoben. Im zweiten Fall wurde die äußerste rechte 1 herausgeschoben (vielleicht in den Übertragsmerker), und eine neue 1 wurde in die äußerste linke Position kopiert, wobei das Vorzeichen der Zahl erhalten blieb. Mehrfache Verschiebungen werden manchmal zu einer einzigen Verschiebung um eine bestimmte Anzahl von Ziffern verkürzt. Zum Beispiel:

 00010111 (decimal +23) LEFT-SHIFT-BY-TWO= 01011100 (decimal +92)

Eine arithmetische Linksverschiebung um n ist äquivalent zur Multiplikation mit 2n (vorausgesetzt, der Wert läuft nicht über), während eine arithmetische Rechtsverschiebung um n eines Zweierkomplement-Wertes äquivalent zur Division durch 2n und Rundung gegen negativ unendlich ist. Wird die Binärzahl als Einerkomplement behandelt, dann ergibt die gleiche Rechtsschiebeoperation eine Division durch 2n und eine Rundung gegen Null.

Logische VerschiebungBearbeiten

Linke logische Verschiebung

Logische Verschiebung nach rechts

Bei einer logischen Verschiebung, werden Nullen eingeschoben, um die verworfenen Bits zu ersetzen. Daher sind die logische und die arithmetische Linksverschiebung genau dasselbe.

Da die logische Rechtsverschiebung jedoch den Wert 0 in das höchstwertige Bit einfügt, anstatt das Vorzeichenbit zu kopieren, ist sie ideal für vorzeichenlose Binärzahlen, während die arithmetische Rechtsverschiebung ideal für vorzeichenbehaftete Zweierkomplement-Binärzahlen ist.

Zirkularverschiebung

Eine weitere Form der Verschiebung ist die Zirkularverschiebung, bitweise Drehung oder Bitrotation.

DrehenBearbeiten

Linke kreisförmige Verschiebung oder Drehung

Rechte kreisförmige Verschiebung oder rotieren

Bei dieser Operation, manchmal auch Rotate No Carry genannt, werden die Bits so „gedreht“, als ob das linke und das rechte Ende des Registers verbunden wären. Der Wert, der bei einer Linksverschiebung nach rechts geschoben wird, ist der Wert, der links herausgeschoben wurde, und umgekehrt bei einer Rechtsverschiebung. Dies ist nützlich, wenn alle vorhandenen Bits erhalten bleiben sollen, und wird häufig in der digitalen Kryptographie verwendet.

Drehen durch CarryEdit

Linksdrehung durch Übertrag

Rechtsdrehung durch Übertrag

Die Rotation durch Übertrag ist eine Variante der Rotationsoperation, bei der das Bit, das (an einem Ende) hineingeschoben wird, der alte Wert des Carry-Flags ist, und das Bit, das (am anderen Ende) herausgeschoben wird, der neue Wert des Carry-Flags wird.

Ein einzelner durchgedrehter Übertrag kann eine logische oder arithmetische Verschiebung um eine Position simulieren, indem das Carry-Flag vorher gesetzt wird. Wenn das Carry-Flag beispielsweise 0 enthält, dann ist x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE eine logische Rechtsverschiebung, und wenn das Carry-Flag eine Kopie des Vorzeichenbits enthält, dann ist x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE eine arithmetische Rechtsverschiebung. Aus diesem Grund haben einige Mikrocontroller, wie z. B. Low-End-PICs, nur Rotate und Rotate-Through-Carry und machen sich nicht die Mühe, arithmetische oder logische Schiebebefehle zu verwenden.

Rotate-Through-Carry ist besonders nützlich, wenn man Verschiebungen auf Zahlen durchführt, die größer als die native Wortgröße des Prozessors sind, denn wenn eine große Zahl in zwei Registern gespeichert wird, muss das Bit, das von einem Ende des ersten Registers verschoben wird, am anderen Ende des zweiten Registers ankommen. Mit Rotate-Through-Carry wird dieses Bit während der ersten Verschiebung im Carry-Flag „gespeichert“ und kann bei der zweiten Verschiebung ohne zusätzliche Vorbereitung eingeschoben werden.

In HochsprachenBearbeiten

In HochsprachenEdit

In Hochsprachen der C-Familie sind die logischen Verschiebeoperatoren „<<“ für Linksverschiebung und „>>“ für Rechtsverschiebung. Die Anzahl der zu verschiebenden Stellen wird als zweites Argument an den Operator übergeben. Beispiel:

x = y << 2;

Das Ergebnis der Verschiebung x nach links um zwei Bits, was einer Multiplikation mit vier entspricht.

Schiebungen können zu implementierungsdefiniertem oder undefiniertem Verhalten führen, daher ist bei ihrer Verwendung Vorsicht geboten. Das Ergebnis einer Verschiebung um eine Bitanzahl, die größer oder gleich der Wortgröße ist, ist in C und C++ undefiniertes Verhalten. Die Rechtsverschiebung eines negativen Werts ist implementierungsabhängig und wird von guter Programmierpraxis nicht empfohlen; das Ergebnis der Linksverschiebung eines vorzeichenbehafteten Werts ist undefiniert, wenn das Ergebnis nicht im Ergebnistyp dargestellt werden kann.

In C# ist die Rechtsverschiebung eine arithmetische Verschiebung, wenn der erste Operand ein int oder long ist. Ist der erste Operand vom Typ uint oder ulong, ist die Rechtsverschiebung eine logische Verschiebung.

Zirkuläre Verschiebungen

In der C-Sprachfamilie fehlt ein Rotationsoperator, aber aus den Verschiebeoperatoren kann einer synthetisiert werden. Es muss darauf geachtet werden, dass die Anweisung gut geformt ist, um undefiniertes Verhalten und Timing-Angriffe in Software mit Sicherheitsanforderungen zu vermeiden. Eine naive Implementierung, die einen 32-Bit-Wert ohne Vorzeichen x um n Positionen nach links rotiert, ist zum Beispiel einfach:

uint32_t x = ..., n = ...;uint32_t y = (x << n) | (x >> (32 - n));

Jedoch, eine Verschiebung um 0 Bits führt zu undefiniertem Verhalten im rechten Ausdruck (x >> (32 - n)), weil 32 - 032 ist, und 32 liegt außerhalb des Bereichs inklusive. Ein zweiter Versuch könnte zu folgendem Ergebnis führen:

uint32_t x = ..., n = ...;uint32_t y = n ? (x << n) | (x >> (32 - n)) : x;

wo der Verschiebungsbetrag getestet wird, um sicherzustellen, dass er kein undefiniertes Verhalten einführt. Die Verzweigung fügt jedoch einen zusätzlichen Codepfad hinzu und stellt eine Möglichkeit für Timing-Analysen und Angriffe dar, was in Software mit hoher Integrität oft nicht akzeptabel ist. Außerdem wird der Code zu mehreren Maschinenbefehlen kompiliert, was oft weniger effizient ist als der native Befehl des Prozessors.

Um das undefinierte Verhalten und die Verzweigungen unter GCC und Clang zu vermeiden, wird Folgendes empfohlen. Das Muster wird von vielen Compilern erkannt, und der Compiler wird eine einzelne Rotate-Anweisung ausgeben:

uint32_t x = ..., n = ...;uint32_t y = (x << n) | (x >> (-n & 31));

Es gibt auch compilerspezifische Intrinsics, die zirkuläre Verschiebungen implementieren, wie _rotl8, _rotl16, _rotr8, _rotr16 in Microsoft Visual C++. Clang bietet einige rotate intrinsics für Microsoft-Kompatibilität, die unter den oben genannten Problemen leiden. GCC bietet keine rotate-Intrinsics an. Intel stellt auch x86-Intrinsics zur Verfügung.

JavaEdit

In Java sind alle Integer-Typen vorzeichenbehaftet, daher führen die Operatoren „<<“ und „>>“ arithmetische Verschiebungen durch. Java fügt den Operator „>>>“ hinzu, um logische Rechtsverschiebungen durchzuführen, aber da die logischen und arithmetischen Linksverschiebungsoperationen für vorzeichenbehaftete Ganzzahlen identisch sind, gibt es keinen „<<<„-Operator in Java.

Weitere Details zu den Java-Schiebeoperatoren:

• Die Operatoren << (Linksverschiebung), >> (Rechtsverschiebung mit Vorzeichen) und >>> (Rechtsverschiebung ohne Vorzeichen) werden als Schiebeoperatoren bezeichnet.
• Der Typ des Schiebeausdrucks ist der promotete Typ des linken Operanden. Zum Beispiel ist aByte >>> 2 äquivalent zu ((int) aByte) >>> 2.
• Wenn der promotete Typ des linken Operanden int ist, werden nur die fünf niederwertigsten Bits des rechten Operanden als Verschiebungsabstand verwendet. Es ist so, als ob der rechte Operand einem bitweisen logischen UND-Operator & mit dem Maskenwert 0x1f (0b11111) unterworfen würde. Der tatsächlich verwendete Schiebeabstand liegt also immer im Bereich von 0 bis einschließlich 31.
• Wenn der promotete Typ des linken Operanden lang ist, dann werden nur die sechs niederwertigsten Bits des rechten Operanden als Schiebeabstand verwendet. Es ist so, als ob der rechte Operand einem bitweisen logischen UND-Operator & mit dem Maskenwert 0x3f (0b111111) unterworfen würde. Der tatsächlich verwendete Schiebeabstand liegt also immer im Bereich von 0 bis einschließlich 63.
• Der Wert von n >>> s ist n rechtsverschobene s Bitpositionen mit Nullverlängerung.
• Bei Bit- und Schiebeoperationen wird der Typ byte implizit in int umgewandelt. Wenn der Byte-Wert negativ ist, ist das höchste Bit eine Eins, dann werden Einsen verwendet, um die zusätzlichen Bytes im int aufzufüllen. Also byte b1 = -5; int i = b1 | 0x0200; ergibt i == -5.

JavaScriptEdit

JavaScript verwendet bitweise Operationen, um jede von zwei oder mehr Einerstelle zu 1 oder 0 auszuwerten.

PascalEdit

In Pascal, sowie in allen seinen Dialekten (wie Object Pascal und Standard Pascal), sind die logischen Links- und Rechtsschiebe-Operatoren „shl“ bzw. „shr„. Auch bei vorzeichenbehafteten Ganzzahlen verhält sich shr wie eine logische Verschiebung und kopiert das Vorzeichenbit nicht. Die Anzahl der zu verschiebenden Stellen wird als zweites Argument angegeben. Zum Beispiel wird im Folgenden x das Ergebnis der Verschiebung von y um zwei Bits nach links zugewiesen:

x := y shl 2;