C++/Tutorial: 8. Bitweise Operatoren

Unser achtes Thema reiht sich nicht wirklich in die Themen der bisherigen Kapitel ein, würde dies aber sonst auch nirgens tun, also bringe ich an dieser Stelle mal einen kleinen Exkurs zu den bitweisen Operatoren ein.

Die Größe integraler Datentypen(und Teile von TR1)

Wie bereits bekannt kennt ein Prozessor keine Datentypen, sondern lediglich Bits und Bytes, jeder Datentyp in C++ besteht aus Bits und Bytes. Manchmal mag es sinnvoll sein selbst mit Bits und Bytes zu arbeiten, aber dafür fehlen uns zur Zeit noch die Mittel. Nehmen wir dafür einmal die integralen Datentypen zur Hilfe, also char, short, int und long. Außer bei char kennen wir die Größe dieser Datentypen nicht, jemand der den Code auf einer 32-Bitmaschiene kompiliert wird außerdem andere Größen für diese Datentypen haben, als jemand der den selben Code auf einer 64-Bitmaschiene kompiliert, aus diesem Grund wäre es nicht gut eine feste Größe für einen integralen Datentypen anzunehmen. Es gibt in C++ zwei Mittel, die wir verwenden können um das ganze etwas allgemeiner zu halten: Wir erfragen die Größe eines Datentyps zur Compilezeit und richten uns dynamisch danach, oder aber wir verwenden integrale Datentypen, von denen wir die Größe sicher wissen.

sizeof

Zunächst die erste Variante: Wir verwenden wie gewohnt unsere ganz normalen Datentypen und wenn wir mit den Bits und Bytes selbst arbeiten wollen erfragen wir uns die Größe und richten unseren Algorithmus danach aus. Nur wie erfragen wir uns die Größe? Die Lösung bietet ein Operator: sizeof. Wir können mit sizeof die Größe von Variablen und Datentypen in Bytes zur Compilezeit erfahren. Syntaktisch kann sizeof wie eine Funktion verwendet werden, als Parameter kann man die Variable verwenden, deren Bytegröße man gerne kennen möchte. Wäre x z.B. eine Integervariable liefert sizeof(x) die Bytezahl von ints auf der Maschiene mit dem Compiler. Wir können im Gegensatz zu Funktionen aber auch gleich den Typen übergeben, sizeof(int) würde genau so funktionieren.

#include <iostream>
 
using namespace std;
 
int main()
  {
  cout << sizeof(int) << endl; //gibt bei mir 4 aus, mag bei euch anders sein.
  }

numeric_limits

Vielleicht für die bitweise Manipulation von Daten weniger wichtig, aber sehr wohl denkbar wäre es, dass wir von unseren integralen Datentypen nicht nur die Bytezahl brauchen, sondern auch die eigentliche Kapazität, also Zahlen in welchem Bereich nun von welchem Typ aufgenommen werden können. An dieser Stelle hilft uns die Standardbibliothek weiter, wir haben es bereits kennen gelernt, aber den Zweck die erklärt: numeric_limits aus dem Header <limits>. Die Syntax zur Verwendung der beiden Funktionen min und max lautet numeric_limits<TYP>::min() bzw. numeric_limits<TYP>::max(). min gibt dabei den kleinsten Wert an, den dieser Typ aufnehmen kann, max den größten.

#include <iostream>
#include <limits>
 
using namespace std;
 
int main()
  {
  cout << numeric_limits<int>::max() << endl; //gibt bei mir 2147483647 aus, größere Werte kann int nicht annehmen
  }

cstdint

Das Programm so flexibel zu programmieren, dass die Größe der Datentypen egal ist, ist natürlich ideal, aber manchmal nicht möglich, manchmal wollen wir die Größe unserer Datentypen einfach selbst bestimmen.

Technical Report 1

TR1 tauchte bereits im Titel dieses Kapitels auf und nun wieder, aber was ist das eigentlich? Die Sache ist die, dass Standard-C++ für das angesprochene Problem keine Standardlösung bereithält, aber es gibt eine Lösung im TR1. Der TR1 (Technical Report 1) ist eine ebenso standardisierte Erweiterung des C++ Standards, die 2003 erschienen ist, auch wenn sich dieses C++-Tutorial auf den Standard beschränkt wird es den TR1 ebenso verwenden, denn zum einen ist es ja quasi Standard und zum anderen wird der kommende C++ Standard (Arbeitstitel "C++0x") den TR1 fast unverändert enthalten. Der TR1 ist nicht bei jedem Compiler enthalten, für MSVC muss man ihn sich beispielsweise erst runterladen, der GCC enthält den Technical Report bereits, eine allgemeine implementierung befindet sich in der boost-Bibliothek, die sowieso jeder C++ Programmierer nutzen sollte. Für alle die Gründe haben sich den TR1 nicht zuzulegen: alle Kapitel die den TR1 betreffen werde ich entsprechend markieren, sie können problemlos übersprungen werde.

back to cstdint

Aber gut, was bietet der TR1 uns denn nun für eine Lösung? Der TR1 enthält einige Header aus dem neusten C Standard(C99, der neuer ist als der erste C++-Standard), dieser bietet mit dem Header <cstdint> eine Lösung. cstdint enthält integrale Datentypen mit fixen Größen, wie zum Beispiel int32_t für einen festen signed int mit der Größe von 4 Bytes. Es handelt sich hierbei lediglich um typedefs, nicht um komplett neue Typen! Bei meinem Compiler könnte int32_t z.B. ein Alias für int sein. Eine Auswahl der Typen:

Typ	Beschreibung
int_8t	8-Bit großer vorzeichenbehafter integraler Datentyp
uint_8t	8-Bit großer vorzeichenloser integraler Datentyp
int_16t	16-Bit großer vorzeichenbehafter integraler Datentyp
uint_16t	16-Bit großer vorzeichenloser integraler Datentyp
int_32t	32-Bit großer vorzeichenbehafter integraler Datentyp
uint_32t	32-Bit großer vorzeichenloser integraler Datentyp

Das Prinzip dahinter sollte nun klar sein, aber noch können wir die Typen nicht verwenden, denn <cstdint> ist eine Lüge, so mag der Header in C++0x heißen, aber im Technical Report ist der Name des Headers <tr1/cstdint>. Ähnliches gilt für den namespace, ein using namespace std; reicht nicht mehr, wir benötigen zusätzlich noch ein using namespace std::tr1;

#include <iostream>
#include <tr1/cstdint>
 
using namespace std;
using namespace std::tr1;
 
int main()
  {
  int32_t fixed_size_integer(2147483647); //hart an der 32-Bit Grenze
  cout << fixed_size_integer << endl; //muss noch funktionieren
  }

Bitweise Operatoren

Nun, da wir uns um die Anzahl der Bytes und Bits in einer Zahl kümmern können, widmen wir uns mal der Manipulation dieser, dafür gibt es eine Reihe Operatoren: &,|,^,~,<< und >>.

Bitweises Und &

Ich denke am einfachsten ist es, die Operatoren einzeln abzuarbeiten, fangen wir also mit dem ersten an &, das bitweise Und. Das bitweise Und hat durchaus Ähnlichkeiten mit dem logischen Und, wenn wir uns nämlich anschauen auf was das logische Und arbeitet, werden wir feststellen, dass es sich ebenfalls nur um 2 Werte handelt, true und false. Bei Bits sieht dies genauso aus: 1 und 0, true und false. Aber wie arbeitet das bitweise Und nun? Es tut genau das was das logische Und tut, nur eben bitweise, das heißt, es wird auf jedes Bit einzeln angewand. Am einfachsten ist die an einem Beispiel zu erklären, schauen wir uns mal eine normale 1-Bytegroße Zahl an z.B. 243, die bitweise Darstellung wäre 11110011. Und noch eine, zum Beispiel 63: 00111111 nun wenden wir das bitweise und an:
11110011 &
00111111
- - - - -
00110011 = 51

Es wird also wirklich auf jedes Bitpaar ein "und" angewendet und das Resultat sind ist ein Byte, das nur die Bits gesetzt hat, die beide anderen Bytes auch gesetzt haben, das Resultat wäre also 51. Schnell wird klar, dass von 243 und 63 auf 51 zu schließen nicht wirklich Sinn macht, sinnvoll sind die bitweisen Operatoren wirklich nur, wenn man auch mit den Bits arbeiten will, ein Beispiel hierfür am Ende des Kapitels.

Bitweises Oder |

Die funktionsweise des bitweisen Oder | könnte man nun erschließen, natürlich arbeitet es genau wie das bitweise Und, nur eben ist es das Pendant zum logischen Oder, um die Operation auf das selbe Beispiel wie oben anzuwednden (243|63):
11110011 |
00111111
- - - - -
11111111 = 255

Jackpot, 255, alle Bits sind gesetzt, das liegt daran, dass das Resultat des bitweisen Oders alle Bits gesetzt hat, die einer der beiden oder beide Operanden gesetzt haben.

Bitweises Exklusives Oder ^

Die dritte Operation, hat kein Pendant in den logischen Operatoren: das exklusive Oder ^. Das exklusive Oder setzt ein Bit genau dann, wenn es bei genau einem der beiden Operanden gesetzt ist. In unserem Beispiel, also 11110011 ^
00111111
- - - - -
11001100 = 204

Warum kennt C++ ^ nicht auch als logischen Operator?
Die boolesche Terminologie, kennt das exklusive Oder zwar, ebenso wie das "normale" Oder, aber C++ hat es nur bitweise integriert, das liegt daran, dass man die bitweisen Operatoren auf auf boolesche Werte verwenden kann. Beim logischen Und und dem logischen Oder ist es nicht zwingend notwendig beide Operanden auszuwerten, beim exklusiven Oder ist dies immer notwendig, also kann man gleich effektiv ^ auf boolesche Variablen anwenden. Das ist natürlich etwas unsicherer(in C war eine derartige Art von Sicherheit noch nicht wichtig), denn wenn es sich nicht um 1 oder 0, true oder false handelt ist das Resultat nicht das gewünschte, wenn man auf Nummer sicher gehen will, kann man die beiden Operanden vorher noch mit ! negieren.

Negation ~

Fehlt uns bei den logischen Operationen noch ein Äquivalent zum ! und dieses gibt es natürlich auch: ~. ~ negiert jedes einzelne Bit des Operanden. ~204 wäre also ~11001100
=00110011=51

Shiftoperatoren << und >>

Die letzten beiden Operatoren << und >> sollten euch bekannt vorkommen, aber hier haben sie nichts mit Streams zu tun, sondern hier sind sie in ihrer ursprünglichen Bedeutung anzutreffen. Anwand auf integrale Variablen handelt es sich nämlich um die sogenannten Shiftoperatoren. Die Shiftoperatoren verschieben die Bytes um die angegebene Anzahl an Stellen.
Nehmen wir mal die Zahl 4 und shiften sie um 2 nach rechts:
4 >> 2 = 1
warum?
00000100 >> 2 = 00000001.
<< funktioniert dann natürlich in die andere Richtung. Ich denke die Funktionsweise ist relativ klar, aber was passiert eigentlich an den Enden? An dieser Stelle habe ich 0en eingefügt, ist das immer so? Die Antwort ist nein, wenn wir nach links shiften ist es allerdings so, wenn wir nach links shiften wird immer eine 0 angefügt, wenn wir nach rechts shiften und es sich um einen unsigned Typen handelt ist dies auch so, wenn es sich um einen signed Typen handelt ist das Bit, das am weitesten links liegt normalerweise für das Vorzeichen verantwortlich und dieses wird beibeihalten!

Ein praktisches Beispiel

Wenn man sich die bitweisen Operatoren so ansieht wird man sich denken, dass man diese vermutlich nie braucht und in der Tat kommt dies sehr selten vor, aber es gibt dennoch ein praktisches Beispiel in dem ein paar von diesen Operatoren angewand werden können(Auch wenn es oft bessere Lösungen gibt). Nehmen wir als Beispiel mal Statuseffekte in Spielen, gehen wir davon aus, dass wir den Status eines Spielers speichern möchten, er könnte zum Beispiel vergiftet sein, brennen, oder gar doppelten Angriff haben. Es mag Nahe liegen hier eine enum zu verwenden, aber wenn man näher hinsieht funktioniert das nicht wirklich gut, denn was wenn ein Spieler vergiftet ist und doppelten Angriff hat? Wir könnten nun boolesche Variablen für jeden Statuseffekt verwenden, das ist auch durchaus legitim, aber vielleicht etwas unpraktisch, wenn wir es zum Beispiel einer Funktion übergeben wollen. Eine Möglichkeit wäre hier bits als Flags(bools) zu verwenden, jedes Bit indiziert einen Statuseffekt: 00000001 ist vergiftet sein, 00000010 ist brennen und 0000100 ist doppelter Angriff. Mithilfe der bitweisen Operatoren können wir das nun bewerkstelligen.

#include <iostream>
 
using namespace std;
 
typedef unsigned char state_t;
state_t poisoned(0x01);
state_t burning(0x02);
state_t doubled_atk(0x04);
 
void print_state(state_t state)
  {
  if(state & poisoned)
    cout << "Sie sind vergiftet" << endl;
  if(state & burning)
    cout << "Sie brennen" << endl;
  if(state & doubled_atk)
    cout << "Sie haben doppelten Angriff" << endl;
  }
 
int main()
  {
  print_state(poisoned | doubled_atk);
  }