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.

[Ghostwalker]

Gute Sache Endlich ein Punkt wo ich immer mal nachguggen kann (komme da immer durcheinander )

Kleine Ergänzung:

In der JCL gibts die Unit JCLLogic die u. a. das Arbeiten mit Bitmasken verschiedener größen (Byte bis Int64) sehr erleichtert

[DeddyH]

Hallo,

da kann man mal sehen, hab mir gestern erst die aktuelle JCL und JVCL gezogen, aber das wusste ich noch nicht. Danke für den Tipp

[negaH]

Als Ergänzung noch:

Die heutigen CPUs arbeiten alle intern mit Zahlen in Binärer Darstellung. Eine beliebige Zahl setzt sich also aus einzelnen Ziffern zusammen und deren Position in der Zahl bestimmt deren Wertigkeit. Also ganz einfach die Dezimale Zahl 4321 ist gleich 4*10^3 + 3 * 10^2 + 2*10^1 + 1 * 10^0. Die Potenzen stellen die Wichtingen der Ziffern dar und die 10 die Basis unserer Zahlendarstellung.
Auf Binärrechnern besteht also ein Byte = 8 Bits aus folgenden Wichtungen:

Code:

Bit#                   7  6  5  4 3 2 1 0
Potenz zu 2^Bit#     128 64 32 16 8 4 2 1

Es haben sich par Reglen eingebürgert:

1.) man schreibt eine Zahl immer von Links nach Rechts mit der höchstwertigen Ziffer als erstes, dh. ganz rechts steht das LSB -> Low Significant Bit. Die Zahl 4321 = viertausenddreihunderteinundzwanzih schreibt man ja auch 4321 und nicht 1234.

2.) man nummeriert die Bitpositionen in einem Byte immer mit der Postion 0 beginnend und nicht mit 1, also 0'basierter Index. Das macht Sinn da die Position/Index/Wertigkeit eines Bits damit identisch zur Potenzschreibweise wird. Das Bit 0 hat also immer die Wertigkeit 1, egal welche Zahlenbasis vorliegt. Das Bit 3, eg. die Ziffer an Position 3, hat damit immer die Wertigkeit Basis^3 und im Binärsystem 2^3 = 8.

Wenn man zb. 00011101b (das b steht für binär, o für oktal, d für dezimal und h für hexadecimal) ausschreibt sollte man es so machen

0*2^7 + 0*2^6 + 0*2^5 + 1*2^4 + 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 oder eben
0*128 + 0*64 + 0*32 + 1*16 + 1*8 + 1*4 + 0*2 + 1*1 oder
16 + 8 + 4 + 1

Wichtig ist wieder, von Links nach Rechts vom Höchstewertigen zum Nidrigstwertigen. Das ersparrt einiges an Verwirrung, wenn Schlaumeier zb. meinen sie müssten die Bitindizes 1'basiert indzieren statt 0'basiert, oder eben meinen die Reihenfolge in der Schreibweise umdrehen zu müssen. Da ich nicht nur Software entwickle sondern auch im Hobby einiges an Elektronik mache weis ich zb. das besonders in der Elektronik/Datenblättern von CPU/MCU obige 2 Regeln gelten.


Neben den Boolschen Funktionen wie AND,XOR,OR,NOT etc. pp. verstehen heute Rechner auch die Multiplikation/Divison mit einem Wert zur einer Potenz der Zahlendarstellung des Rechners. Es gibt also Befehle die eine Zahl mit Basis^X multiplizieren oder dividieren können. In unserem Falle also mit 2^x. Diese Befehle nennt man Schiebebefehle oder besser Shift-Operations. In Delphi

shl = shift left = * 2^x
shr = shift right = div 2^x

Möchte man nun obige Konstanten wie

Delphi-Quellcode:

const
  flLesen      = 1;
  flSchreiben  = 2;
  flAusfuehren = 4;
  flAnzeigen   = 8;
  flLoeschen   = 16;

deklarieren dann sind diese identisch zu

Delphi-Quellcode:

const
  flLesen      =  1 shl 0;
  flSchreiben  =  1 shl 1;
  flAusfuehren =  1 shl 2;
  flAnzeigen   =  1 shl 3;
  flLoeschen   =  1 shl 4;

Wir haben also die Bitposition innerhalb unseres Bytes direkt benutzt um die Wertigkeiten zu ermitteln.

Eine Funktion die ein Bit in einem Byte setzt könnte nun so aussehen:

Delphi-Quellcode:

procedure SetBit(var Value: Byte; Bit: Integer);
begin
  Value := Value or (1 shl Bit);
end;

Gruß Hagen

[DeddyH]

Hallo Hagen, ich hatte aus Gründen der Klarheit (und der Faulheit ) auf die detaillierte Erklärung von Zahlensystemen und Bitverschiebung verzichtet. Aber so langatmig wie befürchtet ist das gar nicht, wie Du eindrucksvoll bewiesen hast. Danke für die sinnvolle Ergänzung .

[Christian Seehase]

Moin Deddy,

ich hätte da auch noch zwei kleine Ergänzungen
Zum einen struktureller Natur:
Da das Abfragen/Setzen/Löschen wohl den Regelfall darstellen, Negieren wohl nur sehr selten vorkommt (ich kann mich nicht erinnern das bei Flags je gebraucht zu haben), halte ich es für sinnvoll dies erst am Ende zu nennen.

Zum anderen:
Ich sehe oft, dass Flags mit + und - bearbeitet werden, was sehr leicht zu Fehlern führen kann.
Der Grund für mögliche Fehler ist recht einfach:
Wenn eine Konstante bereits mehrere Flags kombiniert (Beispiel: faAnyFile, wie es bei FindFirst benutzt wird) erhält man durch Addition/Subtraktion mit anderen Flags andere Werte als erwartet, wohingegen die Verwendung von or/and not sich hier neutral verhält.
Diese unerwarteten Werte können jetzt verschiedene Effekte erzeugen:

• Der Funktionsaufruf schlägt komplett fehl (i.d.R. mit Fehler 87, falscher Parameter).
  Das wäre nicht weiter tragisch, man muss halt den Fehler finden.
  
• Man fragt etwas ab, und erhält nicht das gewünschte Ergebnis.
  Je nachdem, inwieweit das Ergebnis das Programm steuert, wird auch dieses Fehler in erster Linie mal ärgerlich sein, ansonsten aber nicht weiter schlimm.
  
• Der Funktionsaufruf macht etwas ganz anderes als man möchte. Es wird u.U. eine Datei neu erstellt, obwohl man sie nur öffnen wollte.
  Das nur mal als fiktives Beispiel, aber es zeigt, wohin es führen kann.

[DeddyH]

Moin Christian, Du wirst lachen, bis auf die Reihenfolge hatte ich mir diese Gedanken auch schon gemacht. Ich werde es wohl heute Abend noch einbauen.

[xZise]

Delphi-Quellcode:

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

Müsste dass nicht das sein:

Delphi-Quellcode:

00000101
  and
11101111
   =
00010101

[jfheins]

Nein, das was du da geschrieben hast ist ein not xor oder ein ist gleich

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

[Muetze1]

Man könnte auch noch ergänzen, das ein Set of auch intern in einer Bitmaske dargestellt wird und somit sich manche Bitkonstanten gut als Menge definieren lassen.