Bitweise Operation

Die Bitverschiebungen werden manchmal als bitweise Operationen betrachtet, da sie einen Wert als eine Reihe von Bits und nicht als numerische Größe behandeln. Bei diesen Operationen werden die Ziffern nach links oder rechts verschoben. 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 Bitverschiebungsoperatoren liegen darin, wie sie die Werte der eingeschobenen Bits bestimmen.

Bit addressingEdit

Wenn die Breite des Registers (häufig 32 oder sogar 64) größer ist als die Anzahl der Bits (normalerweise 8) der kleinsten adressierbaren Einheit (atomares Element), häufig Byte genannt, induzieren die Verschiebungsoperationen ein Adressierungsschema für die Bits.Abgesehen von den Randeffekten an beiden Enden des Registers verhalten sich arithmetische und logische Verschiebungsoperationen gleich, und eine Verschiebung um 8 Bitpositionen transportiert das Bitmuster um 1 Byteposition auf folgende Weise:

Linke arithmetische Verschiebung

Rechte arithmetische Verschiebung

Bei einer arithmetischen Verschiebung werden die Bits, die von beiden Enden verschoben werden, verworfen. Bei einer arithmetischen Verschiebung nach links werden Nullen nach rechts verschoben; in einer rechten arithmetischen Verschiebung wird das Vorzeichenbit (das MSB im Zweierkomplement) nach links verschoben, 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 ganz linke Ziffer über das Ende des Registers hinaus verschoben, und eine neue 0 wurde in die ganz rechte Position verschoben. Im zweiten Fall wurde die 1 ganz rechts herausgeschoben (möglicherweise in das Carry-Flag), und eine neue 1 wurde an die Position ganz links kopiert, wobei das Vorzeichen der Zahl beibehalten wurde. Mehrere Schichten werden manchmal um einige Ziffern auf eine einzige Schicht verkürzt. Zum Beispiel:

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

Eine linke arithmetische Verschiebung um n entspricht der Multiplikation mit 2n (vorausgesetzt, der Wert läuft nicht über), während eine rechte arithmetische Verschiebung eines Zweierkomplementwerts um n der Division durch 2n und der Rundung in Richtung negativer Unendlichkeit entspricht. Wenn die Binärzahl als Einsenkomplement behandelt wird, führt dieselbe Rechtsverschiebungsoperation zu einer Division durch 2n und einer Rundung auf Null.

Logical shiftEdit

Logische Verschiebung nach links

Logische Verschiebung nach rechts

In einer logischen Verschiebung werden Nullen eingeschoben, um die verworfenen Bits zu ersetzen. Daher sind die logischen und arithmetischen Linksverschiebungen genau gleich.

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

Circular shiftEdit

Eine andere Form der Verschiebung ist die kreisförmige Verschiebung, bitweise Drehung oder Bitdrehung.

Drehenbearbeiten

Links kreisförmige verschiebung oder drehen

Rechts kreisförmig verschieben oder drehen

Bei dieser Operation, die manchmal als rotate no carry bezeichnet wird, werden die Bits „gedreht“, als ob das linke und rechte Ende des Registers verbunden wären. Der Wert, der während einer Linksverschiebung nach rechts verschoben wird, ist der Wert, der bei einer Rechtsverschiebung nach links verschoben wurde, und umgekehrt. Dies ist nützlich, wenn alle vorhandenen Bits beibehalten werden müssen, und wird häufig in der digitalen Kryptographie verwendet.

Drehen durch Carrybearbeiten

Links drehen durch tragen

Rechts drehen durch tragen

Rotate through carry ist eine Variante der Rotate-Operation, bei der das Bit, das (an beiden Enden) 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 Rotate through Carry kann eine logische oder arithmetische Verschiebung einer Position simulieren, indem vorher das Carry Flag gesetzt wird. Wenn das Carry-Flag beispielsweise 0 enthält, ist x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE eine logische Rechtsverschiebung, und wenn das Carry-Flag eine Kopie des Vorzeichenbits enthält, ist x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE eine arithmetische Rechtsverschiebung. Aus diesem Grund haben einige Mikrocontroller wie Low-End-Bilder nur rotate und rotate through Carry und kümmern sich nicht um arithmetische oder logische Verschiebungsanweisungen.

Rotate through Carry ist besonders nützlich, wenn Verschiebungen für Zahlen durchgeführt werden, die größer als die native Wortgröße des Prozessors sind, da, wenn eine große Zahl in zwei Registern gespeichert ist, das Bit, das von einem Ende des ersten Registers verschoben wird, am anderen Ende des zweiten Registers eingehen muss. Bei Rotate-through-Carry wird dieses Bit während der ersten Schicht im Carry-Flag „gespeichert“ und ist bereit, während der zweiten Schicht ohne zusätzliche Vorbereitung einzuschalten.

C-familyEdit

In Sprachen der C-Familie sind die logischen Verschiebungsoperatoren „<<“ für die Linksverschiebung und „>>“ für die Rechtsverschiebung. Die Anzahl der zu verschiebenden Stellen wird als zweites Argument für den Operator angegeben. Zum Beispiel,

x = y << 2;

weist x das Ergebnis der Verschiebung von y um zwei Bits nach links zu, was einer Multiplikation mit vier entspricht.

Verschiebungen können zu implementierungsdefiniertem oder undefiniertem Verhalten führen. Das Ergebnis der Verschiebung um eine Bitanzahl größer oder gleich der Wortgröße ist ein undefiniertes Verhalten in C und C ++. Das Verschieben eines negativen Werts nach rechts ist implementierungsdefiniert und wird von der guten Codierungspraxis nicht empfohlen; Das Ergebnis des Verschiebens eines vorzeichenbehafteten Werts nach links 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. Wenn der erste Operand vom Typ uint oder ulong ist, ist die Rechtsverschiebung eine logische Verschiebung.

Circular shiftsEdit

Der C-Sprachfamilie fehlt ein Rotate-Operator, aber einer kann aus den Shift-Operatoren 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. Zum Beispiel ist eine naive Implementierung, die einen 32-Bit-Wert ohne Vorzeichen x um n Positionen dreht, einfach:

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

Eine Verschiebung um 0 Bits führt jedoch zu einem undefinierten Verhalten im rechten Ausdruck (x >> (32 - n)), da 32 - 0 32 ist und 32 außerhalb des Bereichs liegt. Ein zweiter Versuch kann zu:

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 bietet die Möglichkeit zur zeitlichen Analyse und zum Angriff, was bei Software mit hoher Integrität häufig nicht akzeptabel ist. Darüber hinaus wird der Code zu mehreren Maschinenbefehlen kompiliert, was häufig weniger effizient ist als die native Anweisung 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 gibt eine einzelne rotate Anweisung aus:

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 grundlegende Intrinsics für die Microsoft-Kompatibilität, bei denen die oben genannten Probleme auftreten. GCC bietet keine rotate Intrinsics. Intel bietet auch x86-Intrinsics.

JavaEdit

In Java sind alle Integer-Typen signiert, sodass die Operatoren „<<“ und „>>“ arithmetische Verschiebungen ausführen. 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 in Java keinen Operator „<<<„.

Weitere Details zu Java Shift Operatoren:

• Die Operatoren << (left shift), >> (signed right shift) und >>> (unsigned right shift) werden als shift Operatoren bezeichnet.
• Der Typ des Shift-Ausdrucks ist der heraufgestufte Typ des linken Operanden. Beispiel: aByte >>> 2 entspricht ((int) aByte) >>> 2.
• Wenn der hochgestufte Typ des linken Operanden int ist, werden nur die fünf Bits niedrigster Ordnung des rechten Operanden als Verschiebungsabstand verwendet. Es ist, als ob der rechte Operand einem bitweisen logischen UND-Operator & mit dem Maskenwert 0x1f (0b11111) unterzogen würde. Der tatsächlich verwendete Schaltweg liegt daher immer im Bereich von 0 bis einschließlich 31.
• Wenn der hochgestufte Typ des linken Operanden lang ist, werden nur die sechs Bits niedrigster Ordnung des rechten Operanden als Verschiebungsabstand verwendet. Es ist, als ob der rechte Operand einem bitweisen logischen UND-Operator & mit dem Maskenwert 0x3f (0b111111) unterzogen würde. Der tatsächlich verwendete Schaltweg liegt daher immer im Bereich von 0 bis einschließlich 63.
• Der Wert von n >>> s ist n rechtsverschobene s-Bitpositionen mit Nullerweiterung.
• Bei Bit- und Shift-Operationen wird der Typ byte implizit in int konvertiert. Wenn der Bytewert negativ ist, ist das höchste Bit eins, dann werden Einsen verwendet, um die zusätzlichen Bytes im int zu füllen. Also Byte b1 = -5; int i = b1 | 0x0200; ergibt i == -5 .

JavaScriptEdit

JavaScript verwendet bitweise Operationen, um jede von zwei oder mehr Einheiten gleich 1 oder 0 auszuwerten.

PascalEdit

In Pascal sowie in all seinen Dialekten (wie Object Pascal und Standard Pascal) sind die logischen Links- und Rechtsverschiebungsoperatoren „shl“ bzw. „shr„. Selbst für Ganzzahlen mit Vorzeichen 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 weist das Folgende x das Ergebnis der Verschiebung von y um zwei Bits nach links zu:

x := y shl 2;