Verschiebe-Operationen

Die Bit-Operationen sollten für den Artikel soweit bekannt sein. Hier beschäftigen wir uns mit dem Verschieben von Bits und werden die Bit-Operationen für die Beispiele verwenden.

Die Grundlagen

Die Bitverschiebung ist eine sehr einfache Operation, die wir im Alltag auch gut kennen. Der Computer arbeitet mit dem dualen (2er) Zahlensystem, während Menschen in der Regel im dezimalen (10er) Zahlensystem rechnen. Wenn wir eine Ziffer um eine Stelle nach links verschieben wollen, dann multiplizieren wir im dezimalen Zahlensystem mit 10. Wollen wir nach rechts verschieben, so teilen wir durch 10. Genauso funktioniert das Bit-Verschieben beim Computer. Da wir im dualen Zahlensystem arbeiten multiplizieren wir jedoch mit 2 statt mit 10.

-7- -6- -5- -4- -3- -2- -1- -0-
5
*
4
0 0 0 0 0 1 0 1 entspricht dem Wert 5 logisch true
* multiplizieren
0 0 0 0 0 1 0 0 entspricht dem Wert 4 logisch true
ergibt 0 0 0 1 0 1 0 0 entspricht dem Wert 20 logisch true

Wir sehen, dass sich das Bitmuster der Zahl 5 um 2 Stellen nach links verschoben hat und auf der rechten Seite mit 0-Bits aufgefüllt wurde. Diese 2 Stellen finden sich auch mathematisch wieder, denn es fand eine Multiplikation mit 22 statt.

Für diese Multiplikation bzw. Division mit dem Exponenten von 2 gibt es in C eigene Operatoren, die aufgrund ihrer Wirkung im Bitmuster als Verschiebe-Operatoren bezeichnet werden.

Bevor wir uns ein Beispiel ansehen, was man mit den Bitschiebe-Operatoren sinnvolles machen kann, ein kurzer Überblick

Die binäre Linksverschiebung

Die binäre Linksverschiebung wird mit dem Operator “«“ beschrieben:

int ergebnis = 5 << 2;


-7- -6- -5- -4- -3- -2- -1- -0-
5
«
2
0 0 0 0 0 1 0 1 entspricht dem Wert 5 logisch true
« links verschieben
0 0 0 0 0 0 1 0 entspricht dem Wert 2 logisch true
ergibt 0 0 0 1 0 1 0 0 entspricht dem Wert 20 logisch true

Auf der rechten Seite werden Nullen eingefügt, was auf der linken Seite herausrutscht, geht verloren.

Die binäre Rechtsverschiebung

Nun schauen wir uns das Gleiche mit der Rechtsverschiebung an. Der Operator heißt hier “»“.

int ergebnis = 5 >> 2;


-7- -6- -5- -4- -3- -2- -1- -0-
5
»
2
0 0 0 0 0 1 0 1 entspricht dem Wert 5 logisch true
» rechts verschieben
0 0 0 0 0 0 1 0 entspricht dem Wert 2 logisch true
ergibt 0 0 0 0 0 0 0 1 entspricht dem Wert 1 logisch true

Das Bitmuster im Ergebnis sieht nun anders aus, denn auch hier werden Nullen aufgefüllt - diesmal von links - und was rechts herausrutscht geht verloren. Die Operation entspricht der Division durch 22, also 5 dividiert durch 4. Das Ergebnis ist 1, denn ein Integer hat schließlich keine Nachkommastellen.

Beispiel

Als Beispiel werden wir uns mit Farbwerten auseinandersetzen: Heute ist die 24-Bit Farbtiefe üblich, bzw. es werden 32-Bit verwendet. Früher wurden Bildschirmauflösungen entweder Indexbasiert dargestellt (2-8 Bit je Pixel) oder es wurden mit 16 Bit Farbtiefe gearbeitet.

Vielleicht erinnern wir uns noch aus dem Kunstunterricht daran, dass Farben sich aus drei Grundfarben zusammensetzen. Falls Du noch nicht weißt, wie sich Farben beim Computer zusammensetzen, lies doch einfach das Kapitel Farben, bevor Du hier weiterliest. Die Grundfarben sind beim Computer Rot, Grün und Blau und bei 24 Bit Farbtiefe werden je 8 Bit für die Intensität einer Farbe verwendet. In einem 32-Bit großen Farbwert sind zusätzlich 8 Bit für einen Alpha-Wert möglich.

Haben wir nun einen 32-Bit breite Farbinformation, so können wir hierfür eine Variable vom Typ unsigned int verwenden. Die Intensität können wir mit 4 unsigned chars beschreiben:

// Sattes Rot, Opak
 
unsigned char alpha = 255;
unsigned char red   =   0;
unsigned char green =   0:
unsigned char blue  = 255;
 
unsigned int colorValue;

Nun stellt sich die Frage, wie man die Farbinformation nun zusammenstellt. Und hier kommen nun die Bit-Schiebe-Operatoren ins Spiel. Schauen wir uns zunächst die 32 Bit des Color-Values an und wie wir die Informationen hier einkodieren wollen.

31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
alpha red green blue

Entsprechend müssen wir nun die 8 Bit-Werte an die richtige Position verschieben und können sie dann „verodern“:

colorValue = ( alpha << 24 ) | ( red << 16 ) | ( green << 8 ) | ( blue << 0 )

Die Verschiebung von blue können wir uns natürlich sparen, ich habe sie lediglich angefügt, damit die Verschiebungen von 8, 16 und 24 Bit vielleicht nachvollziehbar werden. Die eingehenden Variablen sind ja vom Typ unsigned char. Verschiebe ich das 0. Bit von green um 8 Bit, dann landet es auf dem 8. Bit von colorValue. Das 7. Bit von green wird ebenfalls um 8 Bit nach links verschoben und landet damit auf Bit 15 bei colorValue. Und so ergibt es sich, dass das 0. Bit von red um 16 Bit verschoben sich bei colorValue direkt am 7. Bit von green anschließt.

Machen wir zur Demonstration entsprechende Funktionen daraus. Die Rücktransformation verläuft entsprechend.

unsigned int createColor( unsigned char alpha, 
    unsigned char red, unsigned char green, unsigned int blue )
{
  return ( alpha << 24 ) | ( red << 16 ) | ( green << 8 ) | ( blue << 0 );
}
 
unsigned int decodeColor( unsigned int color, unsigned char * alpha, 
    unsigned char * red, unsigned char * green, unsigned char * blue )
{
  *alpha =   color >> 24;
  *red   = ( color >> 16 ) & 0xFF;
  *green = ( color >>  8 ) & 0xFF;
  *blue  =   color         & 0xFF;
}

Diese Zeilen sehen nun vergleichsweise unterschiedlich aus. Schauen wir uns im Einzelnen an, was passiert. So sieht das fertige colorValue aus.

In der ersten Zeile interessiert alpha:

  *alpha =   color >> 24;
31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
alpha red green blue
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

Dies schieben wir nun um 24 Bit nach rechts und füllen auf der linken Seite mit Nullen auf:

31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
aufgefüllte Nullen alpha
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

Und schon haben wir den richtigen Wert als Rückgabe, den wir als 8 Bit-Wert nach alpha schreiben können.

Schauen wir uns die zweite Zeile an:

  *red   = ( color >> 16 ) & 0xFF;

Und als Bitmuster:

31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
alpha red green blue
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 color
color » 16
aufgefüllte Nullen alpha red
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 color » 16
& 0xFF
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0xFF
ausgelöschte Bits red
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (color » 16) & 0xFF

Wir sehen also, dass die Bits, die uns interessieren (grau hinterlegt) wieder ganz rechts sind und höherwertigen Bits auf 0 gesetzt sind.

Wenn wir uns die Zeile für green ansehen, ist das Prinzip das gleiche wie zuvor. Die Bits für grün stehen 8 Bit weiter rechts und werden entsprechend auch nur 8 statt 16 Bit nach rechts verschoben. Interessant wird es also erst wieder bei der letzten Zeile:

  *blue  =   color         & 0xFF;

Hier sparen wir uns die Bitschieberei (die Verschiebung um 0 Bit spare ich mir hier also auch), da uns ja die 8 Bits ganz rechts interessieren und die bereits genau da liegen, wo wir sie brauchen. Und so löschen wir die höherwertigen Bits einfach aus:

31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
alpha red green blue
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 color
& 0xFF
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0xFF
ausgelöschte Bits blue
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 (color » 16) & 0xFF

Somit haben wir den Blauwert über und die anderen Bits, die hier gestört hätten (der Alphawert in diesem Fall) sind ausgelöscht.

Weiterführendes

Mit der Bitverschiebung lassen sich sehr viele interessante Dinge mit wenig Rechenzeit lösen. Das Beispiel mit den Farben werde ich nochmal mit einer Bit-Field-Struktur erklären, aber da passiert im Hintergrund schlussendlich genau das, was wir hier behandelt haben.

Es braucht in der Regel etwas Erfahrung, bis man mit den binären Operatoren und den Bitschiebe-Operatoren gut vertraut ist. Also spielt ruhig damit und probiert aus. Zum Experimentieren und verstehen lässt sich die binaryprint()-Funktion verwenden.

Mit der Bitverschiebung lassen sich viele interessante Algorithmen implementieren, gewissermaßen überall da, wo Daten bitweise zusammengesetzt werden müssen. Als Beispiele wären hier die UTF-Konvertierung, Base64, was verwendet wird, um binäre Dateien als ASCII-Files per Mail zu verschicken oder wie es die von Lempel-Ziv entwickelten Algorithmen zu Datenkompression.