Bitoperationen

/ Entwicklung /
Lesezeit: 12 Minuten

Bitweise Operationen sind die einfachsten und schnellsten Operationen, die Computer durchführen können, und auf die sich alle höheren Operationen zurückführen lassen. Dieser Artikel befasst sich auf der einen Seite mit den Grundlagen von Bitoperationen und auf der anderen Seite damit, wie und wo man sie praktisch verwenden kann.

In diesem Artikel werde ich viele Zahlenbeispiele geben und dabei meist die binäre Schreibweise zuerst und die dezimale Schreibweise in Klammern dahinter setzen. Wenn nicht anders angegeben verwende ich vorzeichenlose Beispiele (unsigned) auf Basis von einem Byte, also acht Bit.

Operatoren und Verschiebungen

Dieser Abschnitt dient als Auffrischung und ist bewusst kurz gehalten. Computer rechnen mit dem Binärsystem. Menschen rechnen üblicherweise mit dem Dezimalsystem. Zahlen beider Systeme lassen sich leicht ins andere übersetzen. Es gibt vier Operatoren für Berechnungen mit Bits:

  • NOT
  • AND
  • OR
  • XOR (exklusives OR)

NOT invertiert alle Bits, macht also aus 0 den Wert 1 und umgekehrt:

NOT 00011001 (25)
  = 11100110 (230)

In vielen Sprachen, wie etwa Python, Ruby und JavaScript, ist das Ergebnis nicht 230, sondern -26. Dies liegt daran, dass die Datentypen vorzeichenbehaftet sind, also auch den negativen Zahlenbereich abdecken. In C++ lässt sich das oben angegebene Beispiel wie folgt schreiben:

#include <iostream>

int main() {
	unsigned char x = 25;
	unsigned char y = ~x; // NOT-Operation
	std::cout << (unsigned)y << std::endl;
}

AND, OR und XOR arbeiten jeweils mit zwei Bitfolgen. Für AND gilt: 1 und 1 ergibt 1, alles andere 0. Für OR gilt: 0 und 0 ergibt 0, alles andere 1. Für XOR gilt: 0 und 1 ergibt 1, ebenso 1 und 0, alles andere ergibt 0.

    00011001 (25)
AND 01000011 (67)
  = 00000001 ( 1)

    00011001 (25)
OR  01000011 (67)
  = 01011011 (91)

    00011001 (25)
XOR 01000011 (67)
  = 01011010 (90)

Der Operator NOT wird in vielen Sprachen als Tilde ~ dargestellt, AND als Et-Zeichen &, OR als vertikaler Strich |und XOR als Zirkumflex ^.

Bit-Shifts sind Verschiebungen in einer Bitfolge nach links oder rechts. Sie werden in vielen Sprachen durch die Operatoren << (Verschiebung nach links) und >> (Verschiebung nach rechts) dargestellt, in Pascal aber beispielsweise durch eigene Schlüsselwörter SHL (shift left) und SHR (shift right).

Die folgenden Beispiele zeigen eine Verschiebung um zwei Stellen nach links und eine Verschiebung um eine Stelle nach rechts:

<<2 01000011 (67)
  = 00001100 (12)

>>1 01000011 (67)
  = 00100001 (33)

Das Beispiel zur NOT-Operation in C++ weiter oben ist geeignet, auch diese Verschiebungen nachzuvollziehen, indem ~x durch x << 2 bzw. x >> 1 ersetzt wird. Wie auch beim NOT sind hier der Datentyp und die Vorzeichenbehaftung für das Ergebnis ausschlaggebend. Die beiden Beispiele zeigen, dass aus dem Bereich hinausgeschobene Einsen ersatzlos gestrichen und nachrückende Stellen mit Nullen aufgefüllt werden. Es handelt sich hierbei um eine logische Verschiebung (logical shift). Dem gegenüber gibt es arithmetische Verschiebungen (arithmetic shift), die das Vorzeichen bei einer Verschiebung beibehalten und zyklische Verschiebungen (circular shift), bei denen die Bits rotieren, also rechts verloren gegangene Bits wieder links eingefügt werden und andersrum. Zyklische Verschiebungen werden in der Kryptographie angewandt, z.B. beim AES-Verfahren (Advanced Encryption Standard).

Maskierungen

Bitmasken ermöglichen es, einzelne Bits einer Bitfolge auszulesen oder auf eins oder null zu setzen. Die folgenden Bitmasken verwerfen einen Teil der Bits:

    01000011
AND 00001111
  = 00000011 (die ersten vier Bits sind gelöscht)

    01000011
AND 11110000
  = 01000000 (die letzten vier Bits sind gelöscht)

Die nachfolgende Bitmaske wertet den Status des zweiten Bits aus.

    01000011
AND 01000000
  = 01000000

Diese Bitmaske setzt das dritte Bit, dabei ist es unerheblich ob es bereits gesetzt ist oder nicht:

    01000011
OR  00100000
  = 01100011

Boolesche Algebra

Aus den vier Operatoren lassen sich diverse Gleichungen ableiten:

  • x AND x = x
  • x AND 0 = 0
  • x OR x = x
  • x OR 0 = x
  • NOT NOT x = x
  • x XOR x = 0
  • x XOR y = (x OR y) AND (NOT x OR NOT y)

AND, OR und XOR sind kommutativ, es gilt z.B. x AND y = y AND x. NOT und XOR sind (durch erneute Anwendung) umkehrbar. AND und OR sind irreversibel, ebenso wie logische und arithmetische Verschiebungen.

Verschiebungen um den Wert x entsprechen einer Multiplikation bzw. Division mit bzw. durch den Wert 2x:

 6 << 3 = 6 * 23 = 48
12 >> 1 = 12 / 2 =  6

NAND

In Zusammenhang mit CPUs und Flash-Speicher ist gelegentlich von NAND die Rede. Dieses Akronym steht für NOT AND. NAND-Gatter stellen einen Standardbaustein in der digitalen Schaltung dar, da sich mit ihnen alle logischen Verknüpfungen abbilden lassen (vollständiges Logiksystem). So gelten z.B. x OR y = (x NAND x) NAND (y NAND y) und x XOR y = (x NAND (y NAND y)) NAND ((x NAND x) NAND y).

Anwendungen

Bitoperationen finden sich vor allem in der Systemprogrammierung. Je Hardware-naher die Programmierung ist und je mehr Performance eine übergeordnete Rolle spielt, desto häufiger sind bitweise Operationen anzutreffen.

Eine Bitfolge kann z.B. eine Reihe von Flags (true/false) symbolisieren. Einzelne Flags können über Bitmasken ausgelesen, gesetzt oder gelöscht werden.

Ein anschauliches Beispiel ist die Verwaltung einer Farbe im RGB-Farbraum. Die Farbe kann als 32-Bit-Wert verwaltet werden, wovon der Rot-, Grün- und Blau-Anteil je ein Byte belegen und das vierte Byte für die Lichtdurchlässigkeit (Opazität, Alpha-Wert) verwendet wird.

Ein Farbwert kann also wie folgt repräsentiert werden:

01010111 00101010 10101111 01001010

Aus diesem 32-Bit-Wert lässt sich nun durch Maskierung und Verschiebung der Grünanteil (das zweite Byte) extrahieren:

    RGBA(87,42,175,74)

    01010111 00101010 10101111 01001010 (1462415178)
AND 00000000 11111111 00000000 00000000 (16711680)
  = 00000000 00101010 00000000 00000000 (2752512)

>>16 00000000 00101010 00000000 00000000
   = 00000000 00000000 00000000 00101010 (42)

Bei beiden Beispielen spricht man von Bitfeldern, einem Verbunddatentyp, der einer vorzeichenlosen Ganzzahl entspricht, die als Aneinanderreihung individueller oder gruppierter Bits interpretiert wird.

Ein Reales Beispiel für ein Bitfeld ist st_mode, ein Bestandteil der Struktur des Unix-Systembefehls stat. Das Feld st_mode ist mindestens 12 Bit groß. Drei Bits geben einen von sieben möglichen Dateitypen an, drei mal drei Bits repräsentieren die Berechtigungen.

Rechnen mit Bits

Im Abschnitt Boolesche Algebra habe ich kurz erläutert, was eine Verschiebung mathematisch bedeutet. Verschiebungen sind um ein Vielfaches schneller, als Multiplikationen, sofern der Compiler nicht in der Lage ist, die Berechnung entsprechend zu optimieren, also als Verschiebungen zu behandeln.

Da Verschiebungen immer ein Vielfaches von 2 abbilden, können nicht einfach beliebige Multiplikationen als Verschiebungen ausgedrückt werden. In einigen Fällen lassen sich aber Multiplikatoren als 2x + 2y darstellen. Ein Beispiel:

x * 640 = (x * 29) + (x * 27) = x << 9 + x << 7

In diesem Beispiel kann die komplizierte Multiplikation durch eine einfache Addition ersetzt werden.

Auch Additionen lassen sich durch Bitoperationen abbilden, der Algorithmus ist aber nicht ganz so einleuchtend. Das folgende Beispiel ist in Python geschrieben und deklariert eine Funktion add(), die direkt mit den Summanden 13 und 29 aufgerufen wird:

def add(x, y):
    while (y != 0):
        z = x & y
        x = x ^ y
        y = z << 1
    return x

add(13, 29)

z fungiert als Übertragsbit (carry flag). Die Argumente x und y werden durch die Operationen in einer Schleife solange überschrieben, bis y den Wert 0 erreicht. Zu diesem Zeitpunkt beinhaltet x die Summe der Addition. Die nachfolgenden Rechenschritte verdeutlichen den Ablauf exemplarisch für die Summanden 13 und 29:

z = 00001101 AND 00011101 = 00001101 (z = 13 & 29 = 13)
x = 00001101 XOR 00011101 = 00010000 (x = 13 ^ 29 = 16)
y = 00001101 SHL 1        = 00011010 (y = 13 << 1 = 26)

z = 00010000 AND 00011010 = 00010000 (z = 16 & 26 = 16)
x = 00010000 XOR 00011010 = 00001010 (x = 16 ^ 26 = 10)
y = 00010000 SHL 1        = 00100000 (y = 16 << 1 = 32)

z = 00001010 AND 00100000 = 00000000 (z = 10 & 32 =  0)
x = 00001010 XOR 00100000 = 00101010 (x = 10 ^ 32 = 42)
y = 00000000 SHL 1        = 00000000 (y =  0 << 1 =  0)

Auch für die Multiplikation existiert ein Algorithmus. Dieser greift auf die Addition zurück:

def multiply(x, y):
    z = 0
    while y != 0:
        if (y & 1) != 0:
            z = z + x
        x = x << 1
        y = y >> 1
    return z

Es gibt viele weitere spannende Algorithmen mit Bitoperationen. Der nachfolgende z.B. berechnet den Durchschnitt zweier Zahlen, die als Summe ganzzahlig durch zwei teilbar sind:

(x & y) + ((x ^ y) >> 1)

Beispiel x = 3 und y = 9

    0011 ( 3)
AND 1001 ( 9)
  = 0001 ( 1)

    0011 ( 3)
XOR 1001 ( 9)
  = 1010 (10)

>>1 1010
  = 0101 ( 5)

Addition:

    0001 ( 1) // x
AND 0101 ( 5) // y
  = 0001 ( 1) // z

    0001 ( 1) // x
XOR 0101 ( 5) // y
  = 0100 ( 4) // x

<<1 0001 ( 1) // z
  = 0010 ( 2) // y

    0100 ( 4) // x
AND 0010 ( 2) // y
  = 0000 ( 0) // z

    0100 ( 4) // x
XOR 0010 ( 2) // y
  = 0110 ( 6) // x

<<1 0000 ( 0) // z
  = 0000 ( 0) // y

Die Links am Ende des Beitrags enthalten zahlreiche weitere Bit-Algorithmen.

Fazit

Bitweise Operationen spielen in der systemnahen Programmierung eine großen Rolle und können zur Performanceoptimierung verwendet werden, sei es um die Geschwindigkeit zu erhöhen oder den Speicherbedarf zu minimieren. Wichtig dabei ist zu verstehen, ob es sich wirklich um eine Optimierung handelt oder der Compiler diese Optimierung bereits ohnehin vornimmt. Fundamental ist auch ein Verständnis davon, wie die verwendeten Datentypen verwaltet werden, so dass sich Operationen mit NOT und Verschiebungen auch erwartungskonform verhalten. In C ist das Verhalten bei Verschiebungen z.B. teilweise compilerspezifisch oder undefiniert.

In höheren Programmiersprachen wie Java wird man eher gar nicht bis sehr selten mit Bitoperationen zu tun haben. In jedem Fall gehört für mich aber ein Grundverständnis von Bitoperationen zum Portfolio eines jeden Softwareentwicklers dazu. Denn auch wenn man eigentlich nicht systemnah entwickelt, stolpert man früher oder später über eine Legacy-Software, in der Bitoperationen Anwendung finden.

- Bit-Algorithmen von Sean Eron Anderson
- Bit-Algorithmen von Jörg Arndt
- Linux-Dokumentation des Stat-Systembefehls