Arbeiten auf Bitebene

Vielleicht haben Sie schon einmal direkt mit der Win32-API gearbeitet und sind über eine Funktion gestolpert, die einen ganzzahligen Parameter enthält, in dem aber eine Kombination möglicher Werte angegeben werden kann. Wenn Sie sich darüber gewundert haben und nun wissen möchten, was eigentlich dahintersteckt, dann sollten Sie aufmerksam weiterlesen.

Zunächst ein kurzer Exkurs in die binäre Zahlendarstellung

Die kleinste Einheit in der Informatik ist das Bit. Dies kann genau 2 Zustände annehmen: 0 oder 1. Jeder Zahlentyp besitzt eine bestimmte Bitbreite. Ein Byte etwa besteht aus 8 Bit, eine Word aus 2 Byte, also 16 Bit. Ich werde mich im Folgenden auf ein Byte beschränken, einfach weil ich keine Lust habe, unnötig viele Ziffern zu tippen :-) Das niederwertigste Bit (Bit 0) hat den Wert 1 (=> 2^0) und wird immer ganz rechts dargestellt, je weiterer Stelle nach links verdoppelt sich die Wertigkeit (Bit 1 = 2, Bit 2 = 4 usw.). Der maximale Wert einer vorzeichenlosen Ganzzahl ergibt sich somit rein rechnerisch aus 2^Bitbreite - 1, der einer vorzeichenbehafteten Ganzzahl aus 2^(Bitbreite - 1) - 1. Falls Sie das jetzt verwirrt haben mag, schauen wir uns das Ganze doch einmal an einem praktischen Beispiel an. Nehmen wir z.B. die Zahl 5, welche in binärer Darstellung so aussieht (auf ein Byte, also 8 Bit, ausgerichtet):

00000101

Wenn wir also von rechts nach links durchgehen, dann erhalten wir 1 * 1 + 0 * 2 + 1 * 4 + 0 * 8 usw.
Alle Bits auf 1 gesetzt ergibt dann 255, welches den maximalen Wert eines Bytes darstellt (2^8 - 1, wie weiter oben schon gesagt).

Bitoperatoren

Es gibt folgende Möglichkeiten, um auf Bitebene zu arbeiten:

AND - Vergleich ergibt <> 0, wenn beide Bits gesetzt sind
OR - Vergleich ergibt <> 0, wenn mindestens eins der beiden Bits gesetzt ist
XOR - Vergleich ergibt <> 0, wenn genau eins der beiden Bits gesetzt ist
NOT - Negiert den Wert aller Bits (0 in 1 und vice versa)
shl - Verschiebt alle Bits um die angegebene Anzahl nach links (überzählige Bits fallen weg)
shr - Verschiebt alle Bits um die angegebene Anzahl nach rechts (überzählige Bits fallen weg)

Ein paar Beispiele dazu:

//Zahl := 5 and 4;
00000101 //= 5
00000100 //= 4
========
00000100 //= 4

Das Ergebnis enthält nur die Bits, die in beiden zu vergleichenden Zahlen gesetzt sind.

//Zahl := 5 or 8;
00000101 //= 5
00001000 //= 8
========
00001101 //= 13

Das Ergebnis enthält die Bits, die in mindestens einer der zu vergleichenden Zahlen gesetzt sind.

//Zahl := 13 xor 3;
00001101 //= 13
00000011 //= 3
========
00001110 //= 14

Das Ergebnis enthält nur die Bits, die in der einen Zahl gesetzt und in der anderen nicht gesetzt sind.

//Zahl := not 4;
00000100 //= 4
11111011 //-> negiert = 251 (als Byte)

Alle Bits ändern ihren Wert ins Gegenteil.

//Zahl := 255 shl 2;
11111111 //= 255
11111100 //2 Stellen nach links verschoben = 252

Alle Bits werden nach links verschoben, rechts wird mit Nullen aufgefüllt. Ggf. überzählige Bits (im obigen Beispiel 7 und 6) entfallen dabei, man spricht dann von einem Überlauf.

//Zahl := 13 shr 2;
00001101 //= 13
00000011 //2 Stellen nach rechts verschoben = 3

Alle Bits werden nach rechts verschoben und links mit Nullen aufgefüllt. Auch hier entfallen die Bits, die dabei "aus der Maske geschoben" werden.

Nutzen und Anwendung

Möglicherweise denken Sie gerade: "Das ist ja alles gut und schön, aber wozu brauch ich das?". Nun, es handelt sich hier um die optimale Ausnutzung ganzzahliger Datentypen. Bedenken Sie, dass Sie allein in einem einzigen Byte 8 Boolean-Werte unterbringen können, was dann 256 möglichen Kombinationen entspricht.

Praktisches Fallbeispiel:

Nehmen wir einmal an, wir möchten ein Rechtesystem für unsere Daten implementieren. Mögliche Rechte sollen sein:

Anlegen
Einsehen
Bearbeiten
Löschen
Rechte ändern
Alle genannten

Sie können nun für jedes Recht eine eigene Boolean-Variable deklarieren, oder Sie definieren sich Konstanten und arbeiten dann mit einer Bitmaske (bei 6 Rechten reicht ein Byte vollkommen aus und bietet sogar noch 2 Bits Reserve, hier sogar 3, Erklärung folgt). Deklarieren wir also zunächst unsere Konstanten (achten Sie einmal auf die vergebenen Werte, das Präfix rt soll für Recht stehen):

const
  rtAnlegen    = 1;
  rtEinsehen   = 2;
  rtBearbeiten = 4;
  rtLoeschen   = 8;
  rtRechte     = 16;
  rtAlle       = 31;

Fällt Ihnen etwas auf? Falls nicht, hier noch eine nachvollziehbarere Variante:

const
  rtAnlegen    = 1;
  rtEinsehen   = rtAnlegen shl 1;    
  rtBearbeiten = rtEinsehen shl 1;   //oder rtAnlegen shl 2
  rtLoeschen   = rtBearbeiten shl 1; //oder rtAnlegen shl 3
  rtRechte     = rtLoeschen shl 1;   //oder rtAnlegen shl 4
  rtAlle       = rtAnlegen or rtEinsehen or rtBearbeiten or rtLoeschen or rtRechte;

(Falls Ihnen das "Verodern" spanisch vorkommt, schauen Sie sicherheitshalber noch einmal unter Bitoperatoren nach.)
Binär sehen die Konstanten also so aus:

00000001 //= rtAnlegen
00000010 //= rtEinsehen
00000100 //= rtBearbeiten
00001000 //= rtLoeschen
00010000 //= rtRechte
00011111 //= rtAlle

Da rtAlle ja nur eine Kombination aller vorhergehenden Rechte ist, verbleiben uns noch 3 Bit.

In medias res

Gehen wir nun davon aus, dass Sie einem Benutzer alle Rechte außer "Rechte ändern" erteilen möchten. Prinzipiell haben Sie nun 2 performante Möglichkeiten, dies umzusetzen:

Erteilen aller untergeordneten Rechte (verodern)
Erteilen aller Rechte und explizites Entziehen des rtRechte-Rechts

Die 1. Variante ist recht unspektakulär:

User.Rechte := rtAnlegen or rtEinsehen or rtBearbeiten or rtLoeschen;

Die 2. Variante ist da schon interessanter:

User.Rechte := rtAlle and not rtRechte;

Schauen wir uns das einmal im Detail an:

00011111 //= rtAlle
11101111 //= not rtRechte
========
00001111

Kurze Erläuterung: durch das Negieren erreichen wir, dass die Maske alle bis auf die angegebenen Bits enthält. Nun können wir diese mit dem Original AND-verknüpfen und sicher sein, dass das Ergebnis diese Bits ebenfalls nicht enthält, ansonsten aber unverändert bleibt.
Um ein Bit (hier: Recht) "umzuschalten" können Sie das Exklusive Oder (XOR) verwenden. Dabei ist es dann egal, welchen Wert das Bit vorher hatte, nachher entspricht es garantiert dem Gegenteil. Falls Sie mir nicht glauben sollten, hier der Beweis:

User.Rechte := rtAlle; //initialen Stand setzen
User.Rechte := User.Rechte xor rtRechte;

00011111 //= rtAlle
00010000 //= rtRechte
========
00001111 //aktueller Stand, rtRechte ist nicht mehr gesetzt

Nehmen wir diesen Stand und wiederholen die letzte Zuweisung:

User.Rechte := User.Rechte xor rtRechte;

00001111 //= aktueller Stand
00010000 //= rtRechte
========
00011111 //neuer Stand, rtRechte ist wieder gesetzt

Die Prüfung eines bestimmten Bits erledigen wir mittels AND:

if (User.Rechte and rtEinsehen) = rtEinsehen then

Fall 1 (rtEinsehen ist gesetzt):

00011111 //= rtAlle
00000010 //= rtEinsehen
========
00000010 //= rtEinsehen

Fall 2 (rtEinsehen ist nicht gesetzt):

00011101 //= rtAlle ohne rtEinsehen
00000010 //= rtEinsehen
========
00000000 //= 0

Fassen wir zwischendurch zusammen:

Setzen bzw. Kombinieren von Bits geschieht mit OR
Nullen von Bits geschieht mit AND NOT
Umschalten von Bits geschieht mit XOR
Auswerten von Bits geschieht mit AND
Negieren ganzer Bitmasken geschieht mit NOT

Was Sie vermeiden sollten

Erliegen Sie bitte nicht der Versuchung, auf Bitebene zu addieren oder subtrahieren (obwohl man das sogar manchmal in Fachbüchern so liest).
Kurz zum Hintergrund: bei der Addition zweier Bits passiert Folgendes:

0 + 0 = 0
0 + 1 = 1
1 + 1 = 0 + Übertrag auf das nächsthöhere Bit

Bei der Subtraktion hingegen

0 - 0 = 0
0 - 1 = 1 + negativer Übertrag auf das nächsthöhere Bit
1 - 1 = 0

Bei der Addition geht das in die Hose, wenn das Bit bereits gesetzt war:

User.Rechte := rtAlle + rtAnlegen;

00011111 //= rtAlle
00000001 //= rtAnlegen
========
00100000 //neuer Stand, überhaupt nicht definiert

Bei der Subtraktion bekommen Sie ein Problem, wenn das Bit nicht gesetzt war:

User.Rechte := rtAlle - rtAnlegen;

00011110 //= rtAlle ohne rtAnlegen
00000001 //= rtAnlegen
========
00011101 //rtAnlegen ist weiterhin gesetzt, dafür rtEinsehen nicht mehr

Um solche Effekte zu vermeiden haben Sie 2 Möglichkeiten:

Vorherige Prüfung
Verzicht auf Addition/Subtraktion

Nur der Vollständigkeit halber 2 Implementationen der 1. Möglichkeit:

if (User.Rechte and rtAnlegen) = 0 then
  User.Rechte := User.Rechte + rtAnlegen;

if (User.Rechte and rtAnlegen) = rtAnlegen then
  User.Rechte := User.Rechte - rtAnlegen;

Ganz unter uns: wozu sich das antun, wenn es auch anders geht? ;-)

Fortgeschrittene Benutzung

Sie können Bitmasken auch in verschiedene Teile aufspalten, die jeweils eine andere Bedeutung haben sollen. Nehmen wir einmal an, Sie möchten in einer Bitmaske Formatierungsoptionen hinterlegen. Zur Verfügung stehen sollen dabei 16 Farben und 16 Zeichenstile. Ob Sie es nun glauben oder nicht: das passt alles in ein einziges Byte. Definieren wir einmal ein paar Konstanten:

const
  //Farben
  frSchwarz = 0;
  frRot     = 1;
  frBlau    = 2;
  frGruen   = 3;
  //usw.
  frWeiss   = 15;
  
  //Zeichenstile (wieso ich wieder bei 0 beginne, erkläre ich gleich)
  zsFuellen     = 0;
  zsSchraffiert = 1;
  //usw.
  zsGerastert   = 15;

Für 16 Werte benötigen wir 4 Bit (= 1 Halbbyte, auch Nibble genannt). Also legen wir fest, dass das niederwertige Nibble (Bits 0 bis 3) die Farbe bestimmt und das höherwertige (Bits 4 bis 7) den Zeichenstil. Das bedeutet dann aber, dass wir beim Setzen/Auswerten auch darauf achten müssen, das jeweils richtige Nibble (und nur das) zu beachten. Die in meinen Augen einfachste Möglichkeit ist, für den Zeichenstil das Bit-Shifting (shl bzw. shr) einzusetzen. Aus diesem Grund habe ich in der Konstantendefinition wieder bei 0 begonnen, da wir das Nibble somit getrennt setzen/auswerten. Setzen wir doch einmal spaßhalber die Formatierung auf rot und schraffiert.

Format := frRot;
Format := Format or (zsSchraffiert shl 4);

Schauen wir uns das binär in Einzelschritten an:

00000001 //= frRot
00000001 //= zsSchraffiert
00010000 //= zsSchraffiert um 4 Bits nach links verschoben
========
00010001 //= Kombination der beiden Eigenschaften

Für weiß gerastert sähe das dann so aus:

00001111 //= frWeiß
00001111 //= zsGerastert
11110000 //= zsGerastert um 4 Bits nach links verschoben
========
11111111 //= Kombination der beiden Eigenschaften

Auswerten geht dann so:

Farbe := Format and 15; //15 binär = 00001111
Stil := Format shr 4;

//Farbe:
11111111 //= Format(weiß gerastert)
00001111 //= 15
========
00001111 //= 15 (weiß)

//Stil:
11111111 //= Format(weiß gerastert)
00001111 //= Format um 4 Bits nach rechts verschoben (gerastert)

Das soll es an dieser Stelle gewesen sein, ich hoffe, ich konnte Ihnen das Thema verständlich näher bringen. Nun sollten Sie auch wissen, was Sätze wie "The low-order word of lParam specifies the hit-test code." bedeuten.