Bitweise Operatoren: Eine Einführung

Tags:

Als Programmierer müssen wir uns normalerweise nicht um einzelne Bits kümmern. Wir haben eigentlich sogar keinen direkten Zugriff darauf. Der kleinste Datentyp ist das aus 8 Bit bestehende Byte. Wenn wir nun auf ein einzelnes Bit zugreifen wollen, behelfen wir uns den sogenannten bitweisen Operatoren (bitwise operators).

Diese will ich nun vorstellen. In einem weiteren Artikel werde ich dann auf praktischere Anwendungsbeispiele eingehen. Zuerst wollen wir die Grundlagen schaffen.

Inhalt

Anatomie eines Bytes

Schauen wir uns das Byte 10110111 mal genauer an.

Stelle 7 (msb) 6 5 4 3 2 1 0 (lsb)
Speicheradresse X + 7 X + 6 X + 5 X + 4 X + 3 X + 2 X + 1 X
Dualwert 1 0 1 1 0 1 1 1
Dezimalwert 1 * 27 = 128 0 * 26 = 0 1 * 25 = 32 1 * 24 = 16 0 * 23 = 8 1 * 22 = 0 1 * 21 = 2 1 * 20 = 1
Hexadezimalwert 1 * 0x80 0 * 0x40 1 * 0x20 1 * 0x10 0 * 0x08 1 * 0x04 1 * 0x02 1 * 0x01

Jedes Bit in einem Byte hat eine bestimmten Stellenwert, die Bitwertigkeit. Das Bit ganz links entspricht dem sogenannten höchstwertigen Bit (most significant bit), kurz mbs (nicht MSB). Das Bit ganz rechts hingegen ist das niedrigstwertige Bit (least significant bit, lsb).

Dies gilt allerdings nur, wenn ein Byte von rechts nach links gelesen werden soll. Man nennt das lsb 0 und es ist der Normalfall wenn ihr irgendwo eine Binärzahl aufgeschrieben seht. Eine Zählung von links nach rechts heisst msb 0; wobei die Stelle 0 dann ganz links ist, und die Stelle 7 ganz rechts.

Für diesen Artikel gilt lsb 0. Ausserdem hat das msb in diesem Artikel keine spezielle Bedeutung. Das ist wichtig anzumerken, da zum Beispiel bei Fliesskommazahlen das msb als Indikator dafür verwendet wird, ob die Zahl ein Vorzeichen (0 = positive Zahl, 1 = negative Zahl) besitzt. Ihr kennt das auch von MySQL, wo Ganzzahlen (integers) entweder vorzeichenlos (unsigned) oder vorzeichenbehaftet (signed) sein können.

Byte Order

Ein ähnliches System gibt es dann auch noch für Bytes: Die Byte-Reihenfolge (Byte-Order oder Endianness). Werden mehrere Bytes von rechts nach links gelesen nennt sich das Little-Endian. Dabei hat das höchstwertige Byte (most significant byte, MSB) eine eine höhere Speicheradresse als das niedrigstwertige Byte (least significant byte, LSB). Dies ist der Standard auf gewöhnlichen Computern (x86, x64). Das Gegenstück dazu heisst Big-Endian.

Byte 0xAA 0xBB 0xCC 0xDD
Speicheradresse X X + 1 X + 2 X + 3
Little-Endian MSB ... ... LSB
Big-Endian LSB ... ... MSB

Gelesen in Little-Endian ergibt das dann 0xDDCCBBAA und in Big-Endian 0xAABBCCDD. Das Thema wird dann noch viel komplizierter mit Middle-Endian, Mixed-Endian, usw. Kann uns vollkommen egal sein.

Ein Bit isolieren

Bevor wir ein Bit in einem Byte verändern können, müssen wir einen Weg haben, wie wir ein einzelnes Bit in einem Byte repräsentieren können.

Wie ihr bestimmt wisst (oder vorhin nochmals gesehen habt), sagen die Stellen in einer Binärzahl welche Werte der Zweierpotenz "aktiviert" sind und zusammengezählt werden können um eine Dezimalzahl zu bilden. Das hat den netten Effekt, dass wenn nur ein Bit in einem Byte 1 ist, dies einer bestimmten Zahl der Zweierpotenz entspricht.

Stelle Dualzahl Dezimalzahl Hexadezimalzahl
00b0000000120 = 10x01
10b0000001021 = 20x02
20b0000010022 = 40x04
30b0000100023 = 80x08
40b0001000024 = 160x10
50b0010000025 = 320x20
60b0100000026 = 640x40
70b1000000027 = 1280x80

Damit haben wir für jedes Bit in einem Byte einen eindeutigen Identifikator.

Jetzt müssen wir uns aber noch darum kümmern, wie sowas in Code aussehen könnte. Als Beispiel nehme ich PHP.

<?php
// PHP 5.4
$stelle5 = 0b00010000;

// PHP 5.3
$stelle5 = 32;
$stelle5 = pow(2, 5);
$stelle5 = 0x20;
$stelle5 = 1 << 5;

Die Binärnotation in PHP 5.4 ist bestimmt die übersichtlichste. Allerdings kann sie zu einigem Schreibaufwand führen.

Die Dezimalnotation setzt voraus, dass man weiss, dass 25 = 32 ist. Um es nicht selbst auszurechnen können wir uns deshalb der Potenzfunktion pow() behelfen. Diese ist aber nicht immer verfügbar oder im Code zulässig (bspw. PHP Klassenkonstanten).

Die Hexadezimalnotation hilft beim Aufschreiben von langen zweier Potenzen, da sie immer nach vier Zahlen ein wiederkehrendes Muster aufweist (0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x0100, ...). Sie hilft also in erster Linie dabei, dass man keine Rechen-/Schreibfehler macht.

Eine tolle Hilfe ist der leftshift Operator. Dieser schiebt alle Bits im linken Operaden um die im rechten Operanden angegebene Anzahl Stellen nach links.

0b00010011 << 1 = 0b00100110
0b00010011 << 2 = 0b01001100
0b00010011 << 3 = 0b10011000
0b00010011 << 4 = 0b00110000

Die Stellen rechts werden mit Nullen aufgefüllt und Bits links einfach über den Rand des Bituniversums geschmissen.

Wenn wir nun die Zahl 1 (0b00000001) als linken Operanden verwenden, können wir mit dem rechten Operanden das lsb einfach an die gewünschte Stelle verschieben.

0b00000001 << 0 = 0b00000001 =   1
0b00000001 << 1 = 0b00000010 =   2
0b00000001 << 2 = 0b00000100 =   4
0b00000001 << 3 = 0b00001000 =   8
0b00000001 << 4 = 0b00010000 =  16
0b00000001 << 5 = 0b00100000 =  32
0b00000001 << 6 = 0b01000000 =  64
0b00000001 << 7 = 0b10000000 = 128

Damit solltet ihr nun die nötigen Mittel haben um ein Bit innerhalb eines Bytes zu identifizieren.

Ein Bit aktivieren

Um ein bestimmtes Bit in einem Byte auf 1 zu setzen können wir das bitweise ODER (bitwise OR) verwenden, welches üblicherweise durch eine Pipe (|) ausgeschrieben wird.

Dieser Operator setzt alle Bits auf 1, die in einem der beiden Operanden auch 1 sind.

  10110111
| 11110000
----------
= 11110111

Die flinken Köpfe unter euch haben jetzt bestimmt schon bemerkt, dass wenn ein Operand nur aus Nullen besteht, das Resultat dem anderen Operanden entspricht.

  10110111
| 00000000
----------
= 10110111

Das liegt daran, dass beim bitwise OR ein 0 Bit keine Bedeutung hat. Ist ein Bit hingegen eine 1, wird das Resultat an dessen Stellenwert im Resultat immer 1 sein. Mit diesem Wissen können wir in einem Byte jedes beliebige Bit aktivieren, indem wir es mit einem Byte ODER-verknüpfen, wo an der zu aktivierenden Stelle eine 1 steht.

  00000000
| 00100000
----------
= 00100000

  00100000
| 00001000
----------
= 00101000

  00101000
| 00000001
----------
= 00101001

Oder in PHP Code:

<?php
function setBit($byte, $significance) {
    return $byte | 1<<$significance;
}

$byte = 0;                // -> 0b00000000
$byte = setBit($byte, 5); // -> 0b00100000
$byte = setBit($byte, 3); // -> 0b00101000
$byte = setBit($byte, 0); // -> 0b00101001

Ich hab die Leerzeichen im zwischen den Operanden des leftshift Operators übrigens extra weggelassen, damit die Lesbarkeit etwas höher ist.

Ist ein Bit aktiviert?

Als nächsten wollen wir nun überprüfen, ob ein Bit gesetzt wurde. Dafür verwenden wir das bitweise UND (bitwise AND).

Dieser Operator setzt ein Bit nur dann auf 1, wenn es in beiden Operanden auch 1 ist.

  00001111
& 11001100
----------
= 00001100

Das hat natürlich auch zur Folge, dass ein Bit immer 0 ist, wenn die Stelle im rechten Operaden 0 ist. Deshalb können wir wiederum den Trick mit dem "isolierten Bit" anwenden. Diesmal überprüfen wir aber einfach, ob das Resultat grösser als 0 ist; sprich "irgendein" (= unseres) Bit gesetzt ist.

  00001111
& 00000010
----------
= 00000010
> 0
----------
= true

  00001111
& 00100000
----------
= 00000000
> 0
----------
= false

Oder als PHP Funktion.

<?php
function isBitSet($byte, $bit) {
    return ($byte & $bit) > 0;
}

$byte = 0b00001111;
isBitSet($byte, 0x02); // -> true,  weil 2 (0b00000010) > 0
isBitSet($byte, 0x20); // -> false, weil nicht 0 > 0

Bei bitweisen Operationen in Zusammenhang mit Konditionen empfiehlt es sich meist, die Klammern zu setzen. Jedenfalls in PHP. Das obige Beispiel würde ohne Klammern zuerst $bit mit 0 verrechnen.

Alle Bits eines Byte kippen

Wie ihr gleich erfahren werdet will man manchmal alle Bits eines Byte umschalten. Also alle 1 nach 0 und umgekehrt.

Glücklicherweise gibt es dafür wieder einen Operator: Den Einerkomplement-Operator (ones' complement operator oder bitwise complement operator), dargestellt durch eine Tilde (~).

~ 10110111
----------
= 01001000

~ 00000000
----------
= 11111111

Ein Bit in einem Byte kippen

Um ein einzelenes Bit in einem Byte umzuschalten können wir das bitweise Exklusiv-ODER (bitwise XOR), dargestellt durch ein Caret (^), verwenden.

Das XOR setzt Bits nur dort auf 1, wo es in einem der beiden Operanden 1 ist, nicht aber in beiden.

  00001111
^ 00110011
----------
= 00111100

Wir können also ein einzelnes Bit umschalten, indem wir es wie gewohnt einzeln anwenden.

  00001111
^ 00000010
----------
= 00001101

  00001101
^ 00100000
----------
= 00101101

Dazu wieder etwas Code:

<?php
function toggleBit($byte, $bit) {
    return $byte ^ $bit;
}

$byte = 0b00001111;
$byte = toggleBit($byte, pow(2, 1)); // 0b00001101
$byte = toggleBit($byte, pow(2, 5)); // 0b00101101

Ein Bit deaktivieren

Natürlich wollen wir ein Bit auch deaktivieren können. Dazu können wir das bitweise UND in Kombination mit dem Einerkomplement-Operator verwenden. Wir nutzen einen Operanden der alle Bits auf 1 gestellt hat, ausser das Bit, das wir deaktivieren wollen.

  00001111
& 11111011 (~00000100)
----------
= 00001011

Und ein letztes Mal ausprogrammiert:

<?php
function unsetBit($byte, $significance) {
    return $byte& ~(1<<$significance);
}

$byte = 0b00001111;
$byte = unsetBit($byte, 2); // 0b00001011

Zusammenfassung

Nun kennen wir alle nötigen Operatoren um ein Bit auf 1 oder 0 zu setzen, zu überprüfen ob ein Bit 1 oder 0 ist und ein oder mehrere (alle) Bits in einem Byte zu kippen.

Aktion Operator (Symbol) Beispiel
Ein Bit aktivieren Bitweises ODER (|) 0b00001111 | 0b00100000 = 0b00101111
Ein Bit überprüfen Bitweises UND (&) (0b00001111 & 0b00000001) > 0 = true
Alle Bits kippen Einerkomplement-Operator (~) ~0b00000001 = 0b11111110
Ein Bit kippen Bitweises Exklusiv-ODER (^) 0b00001111 ^ 0b00110011 = 0b00110000
Ein Bit deaktivieren Bitweises UND (&) mit Einerkomplement-Operator (~) 0b00001111 & ~0b00000001 = 0b00001110

Wenn alles klappt kommt noch in diesem Jahrhundert ein Folgeartikel zur praktischen Anwendung von bitweisen Operatoren.

Kommentare