Bitwise: Binäre Spielchen

Ich bin hin und wieder erstaunt, wie unbekannt die bitwise Operatoren bei vielen Programmierern doch sind. Gehört hat man davon, vielleicht schon mal einige Beispiele gesehen, doch so richtig verstanden hat man sie doch nicht, selber angewendet sowieso nicht. Desshalb habe ich mich entschieden, diesen kleinen Artikel zu schreiben und hier zu publizieren...

Einführung

Bei modernen Sprachen wie C# merkt man nicht mehr viel von der Hardware, auf dem die Anwendungen schlussendlich ablaufen soll. Konzepte wie das der Objektorientierung abstrahieren von der Architektur des Mikroprozessors besonders stark. Trotzdem stehen auch in C# nützliche Werkzeuge aus der Digitaltechnik zur Verfügung: Bitwise Operatoren. Diese Operatoren sind in CMOS sehr einfach zu implementieren und haben eine konstante Laufzeit da vollständig parallelisierbar. Dafür sind sie umso mächtiger, ist doch ein Mikroprozessor ansich auch nicht viel mehr als eine sinnvolle Verschaltung einzelner CMOS Gatter wie NANDs (negiertes Und), NORs (negiertes Oder), XORs (negierte Gleichheit) oder NOTs (Inversion). Wendet man diese Gatter parallel auf jedes Bit eines ganzen Buses an (der zb, falls 32 Bit breit, gerade eine C# Integer-Zahl repräsentiert), so erhält man die erwähnten bitwise Operatoren. (Einfachheitshalber arbeite ich in diesem Artikel nur mit 8 Bits = 1 Byte).

Binärzahlen

Um bitwise Operatoren zu verstehen ist es unumgänglich, zu Verstehen wie eine Ganzzahl (Integer) als Binärzahl dargestellt wird.

Ein Bit ("eine Datenleitung") kann genau 2 Zustände annehmen: 1 und 0 (vgl. Boolean: 1=true, 2=false). Gruppiert man nun 8 Bits zusammen, so erhält man einen 8 Bit breiten Bus, der 2^8 = 256 verschiedene Zustände, und somit 256 Zahlen darstellen kann. Damit diese Zustände eindeutig Zahlen zugeordnet werden können hat sich eine Konvention (=Code) bewährt, die am einfachsten mit ein par Beispielen gezeigt werden kann:

00000000 = 0
00000001 = 1
00000010 = 2
00000011 = 3
00000100 = 4
00000101 = 5
...
11111111 = 255

Dabei stellt jede Ziffer ein Bit dar; die Ziffer ganz links heist MSB (Most Significant Bit), die ganz rechts LSB (Least Significant Bit).

Das 2er Komplement

Ein C# Integer kann auch negative Zahlen darstellen. Dazu verwendet man das Bit ganz links für das Vorzeichen. Dadurch stehen dann allerdings pro Vorzeichen nur noch 2^7 = 128 verschiedene Zustände zur Verfügung. Mit 8 bits kann man daher, alternativ zum oben vorgestellten (unsigned) Code mit dem Bereich 0..255, auch den (signed) Bereich -128..127 darstellen (0 zählt als positive Zahl, daher ist die grösste positive Zahl 127, nicht 128!). Dazu wieder einige Beispiele:

10000000 = -128
10000001 = -127
...
11111110 = -2
11111111 = -1
00000000 = 0
00000001 = 1
...
01111110 = 126
01111111 = 127

Die positiven Zahlen funktionieren also abgesehen vom ersten Bit genau wie zuvor. Bemerkenswert ist hier vielleicht, dass (-1) + 1 0 ergiebt, 127 plus 1 jedoch (-128)! Doch wie negiert man eine Zahl, zB. '5'? Dazu braucht man erst die Zahl in Binärform. Dann dreht man jedes Bit um (1->0, 0->1) und addiert eine 1:

00000101 = 5
11111010 = -6
11111011 = -5

00000100 = 4
11111011 = -5
11111100 = -4  (beachte hier den Übertrag: 10 + 01 = 11, 101 + 001 = 110, 011 + 001 = 100, 11 + 01 = 00)

00000000 = 0
11111111 = -1
00000000 = 0

Das letzte Beispiel zeigt einen klassischen Überlauf: 011 + 001 = 100. Das führende 1 wird hier jedoch abgeschnitten, da ja kein Platz für eine weitere Stelle vorhanden ist!

Das praktische am 2er Kompelement ist u.a., dass auch die Addition von negativen und gemischten Zahlen genau gleich funktioniert wie bisher, und die Subtraktion sehr einfach auf die Addition mit einem negierten Summanden zurückgeführt werden kann. So lassen sich mit einem simplen Ripple-Carry-Addierer sehr einfach Addier-Subtrahier-Werke mit bereits sehr interessanten Funktionen konstruieren. Damit hat man dann schon fast eine einfache ALU (Arithmetisch Logische Einheit, der Kern jedes Mikroprozessors).

Bitwise Operatoren

In C# stehen folgende bitwise Operatoren zur Verfügung:

• AND/und (a&b): für jedes Bit: 1 wenn a und b beide 1 sind.
• OR/oder (a|b): für jedes Bit: 1, wenn a oder b oder beide 1 sind.
• XOR/exklusives oder (a^b): für jedes Bit: 1, wenn a oder b (aber nicht beide gleichzeitig!) 1 ist.
• INV/komplement (~a): für jedes Bit: 1 wenn a 0 ist, 0 wenn a 1 ist
• SHIFT (a<<n,a>>n): Verschiebt alle Bits um n Stellen nach links bzw. rechts und füll mit 0 auf.

Bitwise Operatoren sind besonders interessant, wenn man in den einzelnen Bits gezielt Informationen hinterlegen will.

Was haben die einzelnen Operatoren nun für Auswirkungen auf den Bus als ganzes, bzw. für was kann man sie in der Praxis gebrauchen?

Der UND Operator '&'

Dieser Operator ist besonders praktisch um einen Bus mit einer Maske zu filtern. Wenn uns zb. nur das 2., 3. und 5. Bit (von rechts) interessiert können wir ihn mit der Maske '00010110' filtern. Alle anderen Bits werden dabei auf 0 gesetzt:

01010101 & 00010110 = 00010100
10101010 & 00010110 = 00000010
00010110 & 00010110 = 00010110
11101001 & 00010110 = 00000000

So kann man z.B. prüfen ob in a=7 das 3. bit gesetzt ist (was hier atsächlich der Fall ist):

int a = 7; //7 = 00000111
if((a & 4) == 4) {//4 = 00000100 Achtung: der linke Teil mus geklammert werden!
    //...
}

Der OR Operator '|'

Mit OR kann man beispielsweise ein Bit oder eine ganze Folge von Bits auf 1 setzen.

Sollen beispielsweise in a=12 das 2. und 3. Bit auf 1 gesetzt werden, so geht das mit folgendem Code:

int a = 12; //12 = 00001100
a = a|6; //6 = 00000110

a hat danach den Wert 14 = 00001110

Der XOR Operator '^'

Damit kann man ein einzelnes Bit oder eine ganze Folge von Bits invertieren.

Sollen beispielsweise das 2. und 3. Bit invertiert werden, so geht das wie folgt:

int b = 6; //6 = 00000110
12^b = 10 //12 = 00001100, 10 = 00001010
14^b = 8 //14 = 00001110, 8 = 00001000
0^b = 6
b^b = 0

Der Komplement Operator '~'

.. ist beispielsweise hilfreich, um ein Bit oder eine Folge von Bits auf 0 zu setzen:

Sollen beispielsweise bei a=12 das 2. und 3. Bit auf 0 gesetzt werden, so geht das wie folgt:

int b = 6; //6 = 00000110 -> ~6 = 11111001
12&(~b) = 8 //12 = 00001100, 8 = 00001000
14&(~b) = 8 //14 = 00001110
0&(~b) = 0
b&(~b) = 0

Was passiert dabei genau? ~b dreht jedes Bit von b um. Somit haben wir genau die inverse Maske. Wir filtern die Eingabe also mit dieser inversen Maske, womit alle Bits, die in b 1 waren, nun im Ergebnis 0 sind.

Hinweis: ~6 = -7. Siehe oben "2er Komplement". -6 ist somit ~6+1!

Die SHIFT Operatoren '<<' und '>>'

Das Shiften ist die schnellste Methode, um eine Zahl n mal mit 2 zu multiplizieren bzw. zu dividieren.:

1<<1 = 2 //00000010
1<<2 = 4 //00000100
3<<2 = 12 //000001100
12>>2 = 3 //00000011

Die Shift Operatoren sind daher auch praktisch um all die oben verwendeten Masken zu generieren. Eine Maske für das 2. und 5. Bit kann beispielsweise wie folgt generiert werden:

(1<<1)|(1<<4) äquivalent mit (00000010)|(00010000) äquivalent mit 00010010, der gesuchten Maske.

Eine klassische Anwendung solcher Masken ist das Subnetting im IP Netzwerkprotokoll ("Subnetmask")

Eine praktische Anwendung der genannten Operatoren: Flags

Enumerationen sind eine praktische Sache. Manchmal wäre es aber besonders praktisch, wenn man auch mehrere Einträge der Enumeration gleichzeitig gewählt werden können. Dazu "dekoriert" man die Enumeration mit dem [Flags] Attribut und weist den Elementen Potenzen von 2 zu (0,1,2,4,8,..,256,..):

[Flags]
public enum AssemblyNameFlags: int
{
    None = 0,
    PublicKey = 1,
    Retargetable = 256
}

Nun kann man man auch durch den OR Operator gemischte Werte zuweisen (a hat danach den Wert 257):

AssemblyNameFlags a = AssemblyNameFlags.PublicKey | AssemblyNameFlags.Retargetable;

Abfragen, ob PublicKey definiert ist:

if((a & AssemblyNameFlags.PublicKey) == AssemblyNameFlags.PublicKey) { code..; }

Das PublicKey Flag nachträglich setzen (falls bereits definiert ändert sich nichts):

a |= AssemblyNameFlags.PublicKey;

Das PublicKey Flag nachträglich entfernen (falls es nicht gesetzt ist ändert sich nichts):

a &= ~AssemblyNameFlags.PublicKey;

Zum Schluss noch ein kleines Code Beispiel

[Flags]
public enum MySuperFlag: int
{
   blue = 1,
   round = 2,
   warm = 4,
   blueAndWarm = 5 // = blue | warm
   ... = 8
   ... = ...
}

MySuperFlag msf = MySuperFlag.blue;
public MySuperFlag SuperFlag //direkter Zugriff auf die Enumeration
{
   set {msf = value;}
   get {return msf;}
}
public bool IsRoundObject //direkter Zugriff auf ein einzelnes Flag der Enumeration
{
   get {return (msf & MySuperFlag.round) == MySuperFlag.round;}
   set
   {
       if(value)
          msf |= MySuperFlag.round;
       else
          msf &= ~MySuperFlag.round;
   }
}