Grundlagen-Tutorial: Bitfield-Arithmetik

Dieser Artikel beschreibt grundlegende Operationen zur Manipulation von Bitfields mit booleschen Operationen. Obwohl dieser Artikel sich auf Java konzentriert, verwenden die meisten Programmiersprachen dieselbe Syntax.

Was ist ein Bitfield?

Alle modernen Computer verwenden binäre Arithmetik – das bedeutet, die kleinste Informationseinheit ist ein Bit – sein Wert kann entweder 0 oder 1 sein. Bei fast allen Hardware-Implementierungen binärer Arithmetik kann man Bits nicht direkt adressieren und modifizieren, sondern muss Bytes (= 8 Bits) verwenden. Bitfields sind Vektoren von Bits, wobei jedes Bit eine bestimmte Information ausdrückt, die entweder wahr oder falsch sein kann. Je nach Anwendung kann das Bitfield mehr oder weniger Platz beanspruchen.

Mögliche Anwendungen für Bitfields umfassen unter anderem Bloom-Filter und Spiel-Künstliche-Intelligenzen. Im letzteren Fall werden sie als Bitboards bezeichnet, wenn sie einen bestimmten Zustand auf einem Spielbrett repräsentieren.

Man kann auch Words (2 Bytes = short in den meisten Konfigurationen), Double Words (4 Bytes = int in den meisten Konfigurationen) oder Quad Words (8 Bytes = long in den meisten Konfigurationen) anstelle einzelner Bytes zur Adressierung verwenden. Auf 64-Bit-Plattformen sind Double Words oder Quad Words normalerweise am effizientesten, aber alles jenseits von Quad Words (d.h. 64 Bits) benötigt mehr als eine CPU-Instruktion, was die Berechnung in der Regel ineffizient macht (es gibt einige Tricks mit SIMD, aber das geht über den Rahmen dieses Artikels hinaus).

Setzen eines oder mehrerer Bits in einem Bitfield

Das Setzen eines einzelnen Bits in einem Bitfield ist extrem einfach, da es nur die boolesche OR-Operation erfordert. Das zu setzende Bit muss zuerst als Maske ausgedrückt werden – wenn $n$ die Nummer des zu setzenden Bits ist, ist die entsprechende Maske $2^n$. Dann kann man den folgenden Ausdruck mit bitweisem (!) OR verwenden, um das Bit zu setzen

bitfield |= mask;

Wenn du mehrere Bits setzen möchtest, verknüpfe einfach alle Masken mit OR wie folgt:

bitfield |= mask1 | mask2 | mask3;

Beachte, dass dieser Code die Bits unabhängig davon setzt, ob sie zuvor bereits gesetzt waren oder nicht.

Bei Verwendung einer beliebigen Programmiersprache sollte immer überprüft werden, dass die bitweisen booleschen Operatoren verwendet werden. C/C++ gibt normalerweise keine Warnung aus, wenn man Operatoren wie || oder && verwendet, aber diese arbeiten nicht bitweise, sondern behandeln die links- und rechtsseitigen Argumente als falsch, nur wenn sie null sind (d.h. kein Bit gesetzt ist).

Zurücksetzen von Bits in einem Bitfield

Das Zurücksetzen von Bits ist fast so einfach wie das Prüfen: Man AND-verknüpft das Bitfield mit der negierten (NOT) Maske. Aufgrund der Funktionsweise der AND- und NOT-Operationen sind die Bits, die in der ursprünglichen Maske nicht gesetzt sind, in der negierten Maske gesetzt und bleiben daher unverändert. Die negierte Maske ist null für die zurückzusetzenden Bits, daher ist das Ergebnis der AND-Operation für diese Bits immer null.

Code-Beispiel:

bitfield &= ~mask;

Wie oben können Masken bitweise mit OR verknüpft werden, um mehrere Zurücksetzungen gleichzeitig durchzuführen – aber denke daran, Klammern darum zu setzen.

bitfield &= ~(mask1 | mask2 | mask3);

Prüfen von Bits in einem Bitfield

Das Prüfen eines Bits in einem Bitfield ist genauso einfach wie das AND-Verknüpfen des Bitfields mit der entsprechenden Maske. Wenn die resultierende Zahl null ist, ist das geprüfte Bit nicht gesetzt, wenn sie nicht null ist, ist das geprüfte Bit gesetzt.

byte result = bitfield & mask;

Wenn du mehrere Masken gleichzeitig verwenden möchtest, beachte, dass das Ergebnis genau dann null ist, wenn keines der den Masken entsprechenden Bits gesetzt ist. Ohne weitere Operationen kann man nicht sehen, wie viele und welche Bits gesetzt sind, wenn mindestens eines gesetzt ist.

byte result = bitfield & (mask1 | mask2 | mask3);

Effizienz von Bitfields und mögliche Alternativen

Offensichtlich benötigen Bitfields etwa 1/8 des Platzes im Vergleich zur Verwendung eines Bytes pro Attribut (die meisten Programmiersprachen verwenden ein Byte pro Attribut bei boolean-Arrays oder ähnlichem). Wenn deine Anwendung deterministischen Speicher benötigt, ist ein Bitfield der platzsparendste unkomprimierte Speichertyp. Da er unkomprimiert ist, müssen keine zeitaufwändigen Komprimierungs- und Dekomprimierungsoperationen durchgeführt werden.

Obwohl Bitfields mindestens eine boolesche Operation pro Lese-/Schreibzugriff benötigen, sind diese Operationen auf allen Prozessortypen extrem schnell (~1 Taktzyklus). Zusätzlich bietet die Verwendung von Bitfields eine deutlich bessere Speicherlokalität (aufgrund der reduzierten Größe) als 1-Byte-pro-Attribut-Speicher und verursacht daher wesentlich weniger Page Faults. Insgesamt führen diese Effekte in fast allen Fällen auf realer Hardware zu einer besseren Zeitleistung, obwohl sie theoretisch etwas langsamer sind als 1-Bit-pro-Attribut-Speicher.

Wenn du eine gewisse Wahrscheinlichkeit für False Positives akzeptieren kannst, solltest du Bloom-Filter als Alternative in Betracht ziehen. Schreiben in sie benötigt mehr Zeit, aber sie benötigen deutlich weniger Platz bei gleichbleibender False-Negative-Wahrscheinlichkeit von null.