Bitweiser Operator – einfach erklärt

Grundidee bitweiser Operationen

Ein bitweiser Operator verarbeitet eine oder zwei Bitketten, Bitfelder, Bitfolgen oder Bitvektoren auf der Ebene einzelner Bits. Binärzahlen können besonders in Programmiersprachen der C-Familie ohne zusätzliche Kennzeichnung als Bitfolgen betrachtet werden. Die Operationen sind schaltungstechnisch sehr einfach; höhere Operationen lassen sich auf sie zurückführen. Dennoch werden sie wegen ihrer geringeren Bedeutung für die Geschwindigkeit eines Computersystems meist weniger stark optimiert als etwa Addition und Subtraktion.

Bei mehrgliedrigen Operanden bedeutet „bitweise“, dass jeweils die Bits an derselben Position komponentenweise verarbeitet werden. Zweistellige bitweise Operationen benötigen Bitfolgen gleicher Länge; unterschiedlich lange Operanden können vom Compiler als Fehler behandelt werden. In C-verwandten Sprachen ist zwischen bitweisen Operationen und logischen, also booleschen, Operationen zu unterscheiden: Logische Operatoren bewerten einen gesamten Wert als true (≠ 0) oder false (= 0), nicht jedes einzelne Bit.

NICHT, UND, ODER und XOR

Bitweises NICHT, auch Komplement, ist einstellig und invertiert jedes Bit: 0 wird 1, 1 wird 0. Als Binärzahl betrachtet entsteht das Einerkomplement. Beispiel: NICHT 0111 = 1000. In C-verwandten Sprachen steht ~ für bitweises NICHT, während ! das logische NICHT ist. So gilt ~5₍dez₎ = ~0101₍bin₎ = 1010₍bin₎ = 10₍dez₎, aber !5₍dez₎ = false.

Bitweises UND verknüpft gleichlange Bitfolgen; ein Ergebnisbit ist nur dann 1, wenn beide zugehörigen Bits 1 sind. Beispiel: 0101 UND 0011 = 0001. Der Operator ist &; logisches UND ist &&. UND dient zur bitweisen Maskierung: Mit einer Maske, die an einer interessierenden Position 1 enthält, kann geprüft werden, ob dieses Bit gesetzt ist. 0011 UND 0010 = 0010; da das Ergebnis nicht Null ist, war das dritte Bit gesetzt. Mit UND und einer invertierten Maske lassen sich Bits löschen: 0110 UND (NICHT 0100 = 1011) ergibt 0010. Außerdem berechnet man eine Binärzahl modulo 2ᵏ, indem man sie mit 2ᵏ−1 UND-verknüpft. Beispiel: 17 mod 8: 010001 UND 000111 = 000001.

Beim bitweisen ODER ist ein Ergebnisbit 0 nur dann, wenn beide zugehörigen Bits 0 sind; sonst ist es 1. Beispiel: 0101 ODER 0011 = 0111. Der Operator ist |, logisches ODER ist ||. ODER setzt gezielt Flags, also Bits, die jeweils eine boolesche Variable darstellen. Beispielsweise setzt 0010 ODER 1000 = 1010 zusätzlich das erste Flag. Dies spart Speicherplatz, wenn viele boolesche Werte verwaltet werden.

Bitweises XOR, dargestellt durch ^, liefert 1 bei unterschiedlichen und 0 bei gleichen Bits: 0101 XOR 0011 = 0110. Logisches XOR wird als ^^ dargestellt. Zwei identische Operanden mit XOR ergeben immer 0; deshalb wird XOR in Assemblersprache gelegentlich verwendet, um ein Prozessorregister auf 0 zu setzen. Mit einer XOR-Maske lassen sich außerdem genau die Positionen umschalten, an denen die Maske eine 1 hat.

Verschiebungen und ihre Bedeutung

Bei bitweisen Verschiebungen werden Bits um eine angegebene Zahl von Positionen nach links oder rechts bewegt. Links bedeutet in der Standardkonvention des Dualsystems Multiplikation, rechts Division durch eine Zweierpotenz. Da Register und Datentypen nur endlich viele Bits besitzen, fallen an einem Ende Bits heraus und am anderen werden Bits eingefügt. <<, teilweise auch shl, bezeichnet eine Linksverschiebung; >> beziehungsweise shr eine Rechtsverschiebung. Barrel-Shifter können Verschiebungen und Rotationen um beliebige Stellenanzahlen schaltungstechnisch realisieren.

Eine Linksverschiebung um n Positionen entspricht einer Multiplikation mit 2ⁿ, sofern keine 1-Bits herausgeschoben werden oder in die Vorzeichenposition gelangen, also kein Ganzzahlüberlauf entsteht. Eine arithmetische Rechtsverschiebung um n Positionen entspricht einer Division durch 2ⁿ; herausgeschobene 1-Bits gehen verloren und Divisionsergebnisse werden abgeschnitten. Beispiel: 12₁₀ = 00001100; 00001100 << 2 = 00110000 = 48₁₀ = 12·2². Eine Verschiebung um 0 verändert den Wert nicht. Soweit Verschiebungen definiert sind, gilt ((xyz) >> m) >> n = (xyz) >> (m+n) und entsprechend für <<.

In C hängt eine Rechtsverschiebung vom Datentyp und gegebenenfalls Vorzeichen ab: Bei unsigned oder nicht-negativen Werten wird mit Nullen, bei negativen signed-Werten gegebenenfalls mit Einsen aufgefüllt. Java bietet dafür >>>, das stets Nullen einfügt. Beispiele sind 00111100 << 1 = 01111000, 01001111 >> 1 = 00100111 sowie 11110000 >> 2 = 11111100 für signed, aber 00111100 für unsigned. 11110000 >>> 2 = 00111100.

Logische, arithmetische und zyklische Verschiebung

Bei der logischen Verschiebung werden herausfallende Bits verworfen und unabhängig von Richtung und Vorzeichen Nullen nachgezogen. Daher sind logische und arithmetische Linksverschiebung – abgesehen von einer möglichen Setzung von Flags – identisch. Die logische Rechtsverschiebung fügt dagegen Nullen statt Kopien des Vorzeichenbits ein und eignet sich für Bitketten oder vorzeichenlose Binärzahlen.

Die arithmetische Verschiebung arbeitet mit vorzeichenbehafteten Zweierkomplementzahlen. Das höchstwertige Bit (MSB) ist das Vorzeichenbit. Beim Rechtsshift werden Kopien dieses Bits eingefügt, sodass das Vorzeichen erhalten bleibt; beim Linksshift werden rechts Nullen eingefügt und links fällt ein Bit heraus. Im 4-Bit-Register gilt 1100 RECHTS-SHIFT um 1 = 1110 und 0110 LINKS-SHIFT um 1 = 1100. Ein Linksshift um n entspricht ohne Überlauf einer Multiplikation mit 2ⁿ. Ein Rechtsshift einer signed-Zahl entspricht einer Division durch 2ⁿ mit Rundung auf die nächstkleinere Zahl, etwa 1>>1 == 1>>31 == 0 und (-1)>>1 == (-1)>>31 == -1.

Bei einer zyklischen Verschiebung oder Rotation sind linkes und rechtes Registerende gedanklich verbunden: Das herausgeschobene Bit wird am anderen Ende wieder eingefügt. Dadurch bleiben alle vorhandenen Bits erhalten. Diese Operation wird unter anderem in Verfahren der digitalen Kryptographie eingesetzt, beispielsweise beim AES-Verfahren („Rijndael“). Bei der zyklischen Verschiebung mit Übertragsbit trennt das Carry-Bit die beiden Enden: Das Carry-Bit wird hineingeschoben, das herausgeschobene Bit wird zum neuen Carry-Bit. Das ist besonders nützlich für Zahlen, die größer als die Wortbreite des Prozessors sind und deshalb auf zwei Register verteilt werden.

Operatoren in Sprachen und Anwendungen

In C und C++ stehen << und >> für Verschiebungen, etwa x = y << 2; Dies ergibt dasselbe wie x = y * 4. Bei unsigned-Werten werden logische Verschiebungen verwendet. Bei signed-Werten ist das Verhalten abhängig von der Implementierung, wenn der rechte Operand negativ ist, ein Linksshift das Vorzeichen ändert oder ein negativer Wert nach rechts verschoben wird. Laut C- und C++-Norm ist das Ergebnis auch undefiniert, wenn die Verschiebeanzahl mindestens so groß wie die Bitbreite der Architektur ist. Auf einer 32-Bit-IA32-Architektur bewirkt y << 32 oft keine Änderung, weil für die Verschiebeanzahl nur 5 Bitstellen vorgesehen sind und damit nur 0 bis 31 korrekt codiert werden können.

In Java sind alle Ganzzahl-Datentypen signed. << und >> sind arithmetische Verschiebungen, >>> ist eine logische Rechtsverschiebung; einen <<<-Operator gibt es nicht. ARM-Assembler verwendet LSL (Logical Shift Left), LSR (Logical Shift Right), ASR (Arithmetic Shift Right), ROR (Rotation ohne Übertragsbit) und RRX (Rotation mit Übertragsbit).

Bitweise Operatoren und Nullvergleiche können auch arithmetische und logische Operationen zusammensetzen. Eine Multiplikation zweier Ganzzahlen a und b lässt sich mit c := 0 ausführen, indem solange b ≠ 0 bei gesetztem niedrigsten Bit von b der Wert a zu c addiert wird, dann a um 1 nach links und b um 1 nach rechts geschoben werden. Das ist schriftliche Multiplikation im Binärsystem, beginnend mit der letzten Ziffer von b. XOR spielt außerdem bei der Gewinnstrategie des Nim-Spiels eine Rolle; die Anzahlen werden dabei sowohl als Binärzahlen als auch als Bitketten behandelt.