Effizientes Arbeiten mit Bitmasken

[DeddyH]

Ich habe mich entschlossen, dieses kleine Tutorial zu schreiben, weil mir in letzter Zeit auffiel, dass viele User mit Bitmasken so ihre Schwierigkeiten haben. Also will ich einmal versuchen, ein wenig Licht ins Dunkel zu bringen.

Wozu braucht man das eigentlich?

Jeder Programmierer wird im Laufe der Zeit auf sog. Flags stoßen (gerade auch im Bereich der Win32-API). In vielen (wenn nicht gar in den meisten) Fällen verbirgt sich dahinter nichts anderes als eine ganze Zahl. Je nach ihrer Breite kann in dieser Zahl eine gewisse Anzahl von Bool' schen Informationen (Attributen) untergebracht werden. Hierzu mal ein kleines Beispiel:

Delphi-Quellcode:

//fiktive Konstanten für die Dateiverarbeitung
const 
  flLesen      = 1;
  flSchreiben  = 2;
  flAusfuehren = 4;
  flAnzeigen   = 8;
  flLoeschen   = 16;

var Flags: byte = 0; //Vorbelegung -> kein Flag gesetzt

Zum Vergleich einmal eine Lösung, die wahrscheinlich viele Anfänger verwenden würden:

Delphi-Quellcode:

//Verwendung einzelner Bool' scher Variablen
var Lesen, Schreiben, Ausfuehren, Anzeigen, Loeschen: Boolean;

procedure TMyForm.FormCreate(Sender: TObject);
begin
  Lesen      := false;
  Schreiben  := false;
  Ausfuehren := false;
  Anzeigen   := false;
  Loeschen   := false;
end;

Auf den ersten Blick ist, abgesehen von der Länge des Quelltextes, kein großer Unterschied erkennbar. Interessant wird es aber spätestens dann, wenn man diese Attribute speichern und wieder auslesen möchte. Nehmen wir als Art der Speicherung einmal die gute alte Ini-Datei. Zum 2. Beispiel könnte diese z.B. so aussehen:

Delphi-Quellcode:

[Attributes]
Lesen=1
Schreiben=0
Ausfuehren=1
Anzeigen=0
Loeschen=0

Nun dasselbe mit dem 1. Beispiel:

Delphi-Quellcode:

[Attributes]
Flags=5

Stellt man sich das Ganze dann noch mit Speicherung in einer Datenbank vor, sollten die Vorteile der binären Lösung (der Bitmaske) jedem klar sein.

Wie wird es benutzt (oder "Binär ist gar nicht schwär")?

Zunächst ein ganz kleiner Exkurs in die binäre Darstellung von Zahlen (der Einfachheit halber lediglich ganzer Zahlen ohne Vorzeichen).
Die kleinste unteilbare Einheit stellt in der Informatik das Byte dar. Jedes Byte besteht aus 8 Bit. Jedes Bit repräsentiert den Wert einer 2er-Potenz (aufsteigend von rechts nach links) und kann entweder den Wert 0 oder 1 annehmen. Das niederwertigste (ganz rechte) Bit hat die Wertigkeit 2^0, was Eins entspricht. Je weiterer Stelle nach links verdoppelt sich diese Wertigkeit.

Nehmen wir als Beispiel mal die Zahl 29, welche in binärer Darstellung so aussieht (auf ein Byte ausgerichtet):
00011101 Errechnet wird das so (von rechts nach links): 1*1 + 0*2 + 1*4 + 1*8 + 1*16 + 0*32 + 0*64 + 0*128
Erweitert man diese Zahl auf Word (= 16 Bit) oder Cardinal (= 32 Bit), so werden lediglich 8 bzw. 24 Stellen nach links mit Nullen aufgefüllt, an der Berechnung ändert sich gar nichts.
Wer Spaß daran hat, kann ja mal alle Bits mit 1 belegen und die resultierende Zahl abfragen oder errechnen. Plötzlich fällt es einem wie Schuppen aus den Haaren, wieso MAXBYTE ausgerechnet 255 ist
Aufmerksame Leser werden bemerkt haben, dass ich in meinem 1. Beispiel die Konstanten so gewählt habe, dass sie Potenzen von 2 entsprechen. Der Grund dafür dürfte nun auch klar sein.

Setzen und Auswerten, aber wie?

In Delphi kennen wir die folgenden binären Operatoren (bitte genau lesen und merken):
and - Das Ergebnis ist dann 1, wenn beide zu vergleichenden Bits 1 sind
or - Das Ergebnis ist dann 1, wenn mindestens eins der zu vergleichenden Bits 1 ist
xor - Das Ergebnis ist dann 1, wenn genau eins der zu vergleichenden Bits 1 ist

Außerdem (für uns in diesem Zusammenhang nicht relevant und daher nur der Vollständigkeit halber erwähnt)
shl - Verschiebung aller Bits um die angegebene Weite nach links
shr - Verschiebung aller Bits um die angegebene Weite nach rechts

Auswerten

Kommen wir zurück zu unserem 1. Beispiel und nehmen an, dass die Variable Flags die Zahl 5 enthält (entspricht Lesen und Ausführen).
Um nun zu ermitteln, ob wir lesen dürfen, bedienen wir uns einer Abfrage wie dieser:

Delphi-Quellcode:

if (Flags and flLesen) > 0 then ...
//Alternativ:
if (Flags and flLesen) = flLesen then ...

Somit findet folgender Vergleich statt (and):

Delphi-Quellcode:

00000101 //Flags
00000001 //flLesen
--------
00000001 // = 1 (flLesen)

Das Ganze funktioniert analog für alle anderen Flags.

Setzen

Hier wird es scheinbar etwas komplizierter.
Wir möchten beispielsweise zusätzlich das Löschen erlauben (in unserem Beispiel 16, d.h. Bit 5 von rechts). Im ersten Impuls würde man vermutlich sagen
Flags := Flags and flLoeschen; Schauen wir uns das wieder in binärer Schreibweise an (and):

Delphi-Quellcode:

00000101 //Flags
00010000 //flLoeschen
--------
00000000 // = 0

*Oops*, das ist aber nicht das beabsichtigte Ergebnis. Wir müssen or verwenden.
Flags := Flags or flLoeschen; Kontrolle (or):

Delphi-Quellcode:

00000101 //Flags
00010000 //flLoeschen
--------
00010101 // = 21

Aha, so sollte das aussehen

Nun wollen wir sicherstellen, dass nicht gelöscht werden darf. Dazu muss ein "and"-Vergleich mit dem negierten Flag durchgeführt werden. Negieren bedeutet hier, dass alle Bits des Flags ihren Wert ändern (0 in 1 und umgekehrt).
Flags := Flags and not flLoeschen; Wir vergleichen (bei gesetztem Flag):

Delphi-Quellcode:

00010101 //Flags
11101111 //not flLoeschen
--------
00000101 // = 5

Und nun bei nicht gesetztem Flag:

Delphi-Quellcode:

00000101 //Flags
11101111 //not flLoeschen
--------
00000101 // = 5

Wie wir sehen, wird das gewünschte Ergebnis in beiden Fällen erreicht.

Um ein bestimmtes Flag zu negieren, kann man das "Exklusive Oder" (xor) verwenden.
Flags := Flags xor flLoeschen; Nach Durchlauf 1 (xor):

Delphi-Quellcode:

00000101 //Flags
00010000 //flLoeschen
--------
00010101 // = 21

Nach Durchlauf 2 (xor):

Delphi-Quellcode:

00010101 //Flags
00010000 //flLoeschen
--------
00000101 // = 5

Fallstricke

Gelegentlich sieht man (sogar in Fachbüchern) die Verwendung von + und - zum Setzen bzw. Entfernen von Flags. Dies erscheint auf den ersten Blick logischer als mit or, and etc. zu arbeiten, denn wir wollen ja eigentlich rechnen. Trotzdem ist davon dringendst abzuraten. Wieso? Der Grund ist ganz einfach der: es funktioniert nur unter ganz gewissen Bedingungen.
Kurz zum Hintergrund: bei der Addition zweier Bits passiert Folgendes:

Delphi-Quellcode:

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

Bei der Subtraktion hingegen

Delphi-Quellcode:

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

Dazu mal ein paar Beispiele:
Flags := Flags + flLoeschen; Ist Bit 4(Loeschen) nicht gesetzt, geht das auch gut (Addition).

Delphi-Quellcode:

00000101 //Flags
00010000 //flLoeschen
--------
00010101 // = 21

Anders sieht es aus, wenn das Flag bereits gesetzt war (Addition).

Delphi-Quellcode:

00010101 //Flags
00010000 //flLoeschen
--------
00100101 // = 37

Umgekehrt (Entfernen des Flags) stellt sich das so dar:
Flags := Flags - flLoeschen; Flag ist gesetzt (Subtraktion):

Delphi-Quellcode:

00010101 //Flags
00010000 //flLoeschen
--------
00000101 // = 5

Flag ist nicht gesetzt (Subtraktion):

Delphi-Quellcode:

00000101 //Flags
00010000 //flLoeschen
--------
11110101 // = 245

Das ist ganz übel: wir haben eine ungewollte Kettenreaktion ausgelöst! Wenn die höherwertigen Bits auch an anderer Stelle im Programm ausgewertet werden, haben wir die Kappe auf. Deshalb mein dringender Rat: niemals so machen .

Das soll es an dieser Stelle gewesen sein. Ich hoffe, dem geneigten Leser ist die Thematik etwas klarer geworden. Außerdem sei auf die Ergänzungen von Hagen verwiesen, was Zahlensysteme und Bitverschiebungen angeht (Nochmals Danke, Hagen).

Für Anregungen, Ergänzungen und sonstige Kritik bin ich immer offen, nur keine Scheu.

//Edit: Ich hatte die Variable im Beispiel Dateiattribute genannt und im Folgenden immer von Flags geredet. Es heißt nun durchgehend Flags. Außerdem habe ich die Anregungen von Christian beherzigt und die Addition und Subtraktion eingefügt.

[xZise]

Zitat von jfheins:

Das and liefert nur 1, wenn beide operanden gleich 1 sind