1. Einführung

Es sollen heute die Bitoperatoren vorgestellt werden. Bitoperatoren greifen direkt auf die binäre Darstellung von Integerzahlen in einer Integer-Variablen zu.

START

2. Die binäre Ebene im Computer

Es heisst zwar immer, der Computer rechne mit 'Einsen' und 'Nullen', also im Binär-Kode, aber bislang machte sich dieser Binär-Kode beim Programmieren noch nicht richtig bemerkbar. In der heutigen Sitzung soll dies anders werden. Es sollen Operatoren (= Funktoren, Funktionen) betrachtet werden, die direkt bei der binären Darstellung des Computers ansetzen.

Was heisst zunächst binäre Darstellung?

Normalerweise kennen wir die dezimale Darstellung von Zahlen. Eine Zahl wie '1504' lesen wir gewöhnlich als Eintausend-Fünfhundert-Vier. Zahlentheoretisch schreibt man diese Zahl als 1*10^3 + 5*10^2 + 0*10^1 + 4*10^0, d.h. man zerlegt die Zahl in absteigende Potenzen zur Basis 10. Man könnte auch schreiben:

Eine allgemeine Fassung für diesen Sachverhalt gibt die folgende Formel:

z = SUM(i=0; n-1) z_i * bⁱ

Ausgeschrieben: z₀ * b⁰ + z₁ * b¹ + ... + z_n-1 * b^n-1

Häufig benutzte Zahlbasen in der Informatik sind:

Zu jeder Zahlbasis b gehören dann auch Zahlzeichen oder Ziffern von 0 bis (b-1), z.B.:

Eine Zahl zur Basis 2 wäre z.B.:

Statt den Ziffern 0...9 hat man im Fall der Basis 2 nur die Ziffern 0 und 1 zur Verfügung. Dies sind nun genau die Zahlen, die auf der untersten Ebene als physikalische Schaltzustände im Computer realisiert werden: die Speicherzellen im Computer sind nach Bytes organisiert, wobei jedes Byte aus 8 Bit besteht, d.h. aus 8 Zellen, wobei jede Zelle entweder den Wert 1 oder 0 haben kann.

Im Fall von 32-Bit-Computern heisst dies z.B., dass eine Zahl vom Typ int in der Sprache C einen Speicherbereich von 4 Bytes * 8 Bits belegt, also 32 Bits. Hätte man nur positive Zahlen, dann liessen sich damit Zahlen bis 2³¹-1 darstellen.

Je nach Speicherarchitektur können die Bits von rechts nach links angeordnet sein (= Big Endian) oder von links nach rechts (Little Endian). Für die logische Nutzung der im nachfolgenden einzuführenden Bitoperatoren spielt dies aber keine Rolle. Im Folgenden wird als Standardfall eine Anordnung von Rechts nach Links angenommen.

Im Fall des Daulsystem sind noch zwei spezielle Zahldarstellungen von besonderer Wichtigkeit: das Stellenkomplement ~z und das 2er-Komplement 2c(z) einer Dualzahl z.

Das Stellenkomplement ergibt sich aus der Nomaldarstellung

z = SUM(i=0; n-1) z_i * bⁱ

Ausgeschrieben: z₀ * b⁰ + z₁ * b¹ + ... + z_n-1 * b^n-1

dadurch, dass man jeden Koeffizienten z_i von 1 subtrahiert, also:

~z = SUM(i=0; n-1) (1-z_i) * 2ⁱ

Ausgeschrieben: (1-z₀) * 2⁰ + (1-z₁) * 2¹ + ... + (1-z_n-1) * 2^n-1

2c(z) = ~z + 1

Beispiele:

Das 2er-Komplement wird benutzt, um negative Zahlen darzustellen. 4 = (0100)₂ und -4 = (1100)₂.

Benutzt man positive und negative ganze Zahlen, dann wird der Bereich der dualen Zahlen wie folgt aufgeteilt:

START

3. Übersicht Bitoperatoren

Folgende Bitoperatoren stehen in ISO-C zur Verfügung:

Die Wirkungsweise dieser Bitoperatoren soll nun im Folgenden erläutert werden.

4. SHIFT-Operatoren

Shift-Operatoren bewegen ein Bitmuster n in einem Bitfeld x Felder nach links (<<) oder nach rechts (>>). Bsp.:

Auf das Bitmuster '00011' wird 3 mal Shift-Links angewendet. Man erhält '11000'. Dann wird auf dieses Muster 3 mal Shift-Rechts angewendet. Man ehält wieder das Ausgangsmuster. Mit dieser Technik kann man auch gezielt nur genau eine 1 über alle Positionen im Bitfeld bewegen und auf diese Weise jede Position mittels eines AND-Operators abfragen (s.u.):

5. Logische Operatoren

Die Bitoperatoren AND, OR, XOR und COMPLEMENT kann man auch als logische Operatoren interpretieren. Ihren Definitions- und Wertebereich kann man in folgenden Tabellen darstellen:

Dies ist wie folgt zu lesen: gegeben sind zwei Bitmuster A und B. Wenn A und B beide den Wert 0 haben, dann liefert A & B = 0, wenn A=0 und B=1, dann liefert A & B = 0, wenn A=1 und B=0, dann liefert A & B = 0, wenn A=1 und B=1, dann liefert A & B = 1. Kurzformel für AND: A & B ist genau dann 1, wenn sowohl A als auch B den Wert 1 haben.

Von logischen Operatoren im Sinne der Aussagenlogik kann man sprechen, wenn man die Werte 1 und 0 als Wahrheitswerte von Sätzen auffasst. Seien also A und B Sätze, die Wahr (1) oder Falsch (0) sein können, dann ist die Aussage A AND B genau nur dann war, wenn beide Sätze wahr sind. Entsprechend für die anderen Operatoren. Das Complement ist im Rahmen einer aussagenlogischen Interpretation dann die Negation. ~A ist falsch, wenn A wahr ist und umgekehrt. Die bekannte Implikation (A --> B) entspricht dann dem Ausdruck (~A | B). Kurzformel für Implikation: A --> B ist genau nur dann falsch, wenn A wahr ist und B falsch.

6. Ein Sherlok Holmes für Bits

In der Praxis werden Bitfelder oft benutzt, um Informationen kompakt zu repräsentieren, d.h. man nimmt Bitfelder einer definierten Länge und weist jeder Position in diesem Bitfeld eine bestimmte Bedeutung zu. in diesem Zusammenhang spricht man dann auch oft von Flags. Eine bestimmte Bit-Position ist dann ein Flag für einen ganz bestimmten Wert. Umgekehrt stellt sich dann aber auch das Problem, wie man gezielt bestimmte Bitpositionen abfragen kann. Angenommen es gäbe ein Bitfeld der folgenden Art:

Die einzelnen Bits werden von verschiedenen Prozessen gesetzt. Ein Prozess P* will jetzt wissen, welche Bits akuell gesetzt sind. Was man hier benötigt ist ein Sherlok Holmes für Bits (nach dem Autor Conan Doyle lebte Sherlok Holmes mit seinem Assistent Doktor Watson von 1881 - 1904 in 221b Baker Street, London). Eine Möglichkeit, einen Sherlok Holmes für Bits zu realisieren ist die folgende:

void bin2str(int n, char *str) {

int i;

for(i=0; i< BITFIELD_LENGTH; i++) {

if (n & (1 << i)) { str[ BITFIELD_LENGTH-1-i]='1'; }

else { str[ BITFIELD_LENGTH-1-i]='0'; }

}

str[ BITFIELD_LENGTH]='\0';

}

Dies ist eine C-Funktion mit Namen bin2str(), da sie eine binäre Darstellung von Bits in eine Zeichenkette von Einsen und Nullen übersetzt. Als Argumente bekommt sie eine Integerzahl n, die (bei 32-Bit-Computern) normalerweise ein Bitfeld von 32 Bits repräsentiert (#define BITFIELD_LENGTH 32), sowie einen Zeiger str, der auf eine Zeichenkette verweist, die eine entsprechende Länge hat (char str[ BITFIELD_LENGTH+1]). Der entscheidende bitentdeckende Part (Sherlok Holmes für Bits!) ist der folgende:

if (n & (1 << i))

Man benutzt die Zahl 1 die mit einem Bit an der Position von 2^0 gespeichert ist, und schiebt diese 1 mittels i jeweils um eine Position nach links. i beginnt mit dem Wert 0 und wird dann jedesmal um 1 erhöht, bis die ganze Breite des Bitfeldes durchlaufen ist. An jeder Poition wird dann mittels AND der Test gemacht 'n & (1 << i)'. Befindet sich an der i-ten Position von n eine 1, dann ist if () wahr, ansonsten falsch. Ist der Test mit if() wahr, dann speichern wir im Protokollstring str an der Stelle BITFIELD_LENGTH-1-i eine '1', ansonsten eine '0'. Ist das Bitfeld durchlaufen, dann wird abschliessend an der stelle BITFIELD_LENGTH eine '\0' angehängt, um das Ende eines Strings zu markieren. Im Ergebnis übersetzt die Funktion bin2str() also eine binäre Zahlendarstellung in eine Zeichenkette von Einsen und Nullen, die sich auf dem Bildschirm ausdrucken lässt (Für eine Anwendung der Funktion bin2str() siehe das folgende Demoprogramm bitoperatoren.c).

7. Anwendungen

Es soll jetzt hier auf einige einfache Anwendungen hingewiessen werden.

/********************
 *
 * bitoperatoren.c
 *
 * author: gdh
 * first: jan-7, 2002
 * last: -
 *
 * FUNKTIONALITAET:
 * Illustration der verschiedenen Bitoperatoren und ein Anwendungsbeispiel
 *
 * Die Integerzahlen werden in n1, n2 und n3 gespeichert.
 * Die entsprechenden Stringrepraesentationen finden sich in nstring, nstring1 und nstring2
 *
 * HILFSFUNKTIONEN
 * void bin2str(int n, char *string) : Uebersetzt eine binaere Zahl in eine Stringrepraesentation
 *
 * KOMPILIEREN: gcc -o bitoperatoren  bitoperatoren.c
 * AUFRUF:  bitoperatoren
 *
 **********************/

#include <stdio.h>

#define NUMBERSTRING_LENGTH 32  /* Der Typ 'int' hat 4 Bytes = 4*8 Bits = 32 Bits */

#define BOLD 1                 /* Beispiel fuer eine Anwendung */
#define UNDERLINE 2        /* Setzen von Attributen */
#define ITALIC 4

int main(void) {

  extern void bin2str(int n, char *str);

  int n,n1,n2;
  char nstring[NUMBERSTRING_LENGTH+1];
char  nstring1[NUMBERSTRING_LENGTH+1];
char  nstring2[NUMBERSTRING_LENGTH+1];
char  nstring3[NUMBERSTRING_LENGTH+1];
char  nstring4[NUMBERSTRING_LENGTH+1];

 unsigned int perc, x1, x2, x3, x4;   /* Fuer Anwendungsbeispiel mit Wahrnehmung */


  while(1) {

    /**********EINGABE ZWEIER INTEGERZAHLEN n1 und n2************/

    printf("\n\n############################\n");

  printf("BITTE ZAHL1: ");
  scanf("%32d",&n1);
bin2str(n1, nstring1);
 printf("Zahl 1:  %d = %s \n",n1,nstring1);


 printf("BITTE ZAHL2: ");
  scanf("%32d",&n2);
bin2str(n2, nstring2);
 printf("Zahl 2:  %d = %s \n",n2,nstring2);


/*************ANWENDUNG VON AND ('&') auf n1 und n2***************/

 n = n1 & n2;
bin2str(n, nstring);
 printf("AND:  %d = %s \n",n,nstring);

 /*************ANWENDUNG VON OR ('|') auf n1 und n2***************/

 n = n1 | n2;
bin2str(n, nstring);
 printf("OR:  %d = %s \n",n,nstring);

 /*************ANWENDUNG VON XOR ('^') auf n1 und n2***************/

 n = n1 ^ n2;
bin2str(n, nstring);
 printf("XOR:  %d = %s \n",n,nstring);

 /*************ANWENDUNG VON KOMPLEMENT ('~') auf n1 ***************/

 n = ~n1;
bin2str(n, nstring);
 printf("KOMPLEMENT von Zahl1:  %d = %s \n",n,nstring);


 /************ANWENDUNGSBEISPIEL MIT EIGENSCHAFTEN****************
  *
  * Jede Eigenschaft bekommt eine eindeutige Kennzahl, z.B.:
  * BOLD 1
  * UNDERLINE 2
  * ITALIC 4
  *
  * Dann kann man mittels OR beliebige Kombinationen setzen:
  *
  *************************/

 /******SETZE EIGENSCHAFTEN, Bsp.1*********/


 n = BOLD | UNDERLINE;

 bin2str(n, nstring);
 printf("\n\nBOLD OR UNDERLINE: %d =  %s\n",n, nstring);


 /*******TEST AUF EIGENSCHAFTEN************/

 if( n & BOLD) printf("BOLD ist gesetzt\n"); else printf("BOLD ist NICHT gesetzt\n");
 if( n & UNDERLINE) printf("UNDERLINE ist gesetzt\n");  else printf("UNDERLINE  ist NICHT gesetzt\n");
 if( n & ITALIC) printf("ITALIC ist gesetzt\n");  else printf("ITALIC  ist NICHT gesetzt\n");


/***************ANWENDUNGSBEISPIEL MIT WAHRNEHMUNG************
*
* Gegeben eine Grid-Welt mit Agenten '#', die eine Zelle einnehmen und visuell
* alle angrenzenden Zellen (0, ..., 7) wahrnehmen koennen.
*
* |--------|
* |-|0|1|2|-|
* |-|7|#|3|-|
* |-|6|5|4|-|
* |--------|
*
* Die Gesamtheit der visuellen Wahrnehmung soll ein Bitfeld perc bilden:
* Je nachdem, ob eines der Felder (0,..,7) besetzt ist, soll im Bitfeld eine
* 1 gesetzt sein oder nicht.
*
* Relativ zu diesem Bitfeld kann man Features definieren, z.B.:
* x1 = 2^1 | 2^2, d.h. wenn Bit 1 oder Bit 2 gesetzt ist, dann
* trifft Feature x1 zu.
*
*  Abhaengig von solchen Features koennte man dann einfache reaktive
*  Aktionen definieren, z.B.
*  if( (perc & x1) && (perc & ~x4) ) Aktion Bewegung nach 'oben'
*
******************************/

    perc =0;
x1 = (1<<1) | (1<<2); bin2str(x1,nstring1);  printf("\nX1: %d =  %s\n",x1, nstring1);
x2 =  (1<<3) | (1<<4); bin2str(x2,nstring2); printf("\nX2: %d =  %s\n",x2, nstring2);
x3 =  (1<<5) | (1<<6); bin2str(x3,nstring3); printf("\nX3: %d =  %s\n",x3, nstring3);
x4 =  (1<<7) | (1<<0); bin2str(x4,nstring4); printf("\nX4: %d =  %s\n",x4, nstring4);

printf("BITTE EINEN WAHRNEHMUNGSVEKTOR: ");
scanf("%32d", &perc);
bin2str(perc,nstring);
 printf("\nWAHRNEHMUNGSVEKTOR: %d =  %s\n",perc, nstring);

if (perc & x1) printf("X1\n"); else  printf("~X1\n");
if (perc & x2) printf("X2\n"); else  printf("~X2\n");
if (perc & x4)  printf("X4\n"); else  printf("~X4\n");
if ( (perc & x1) && (perc & x2) && (perc & ~x4) ) printf("X1 & ~X2 & ~X4\n"); else  printf("~(X1 & ~X2 & ~X4)\n");



  } /* end of while */
} /* end of main */



 /**********UEBERSETZEN DER ZAHLEN IN 1-0-REPRAESENTATION**************/
/*
 * Index  NUMBERSTRING_LENGTH-1-i ist notwendig, um die 1en und 0en
 * von rechts nach links anzuordnen
 *
 **********************************************/

void bin2str(int n, char *str) {

  int i;

  for(i=0; i< NUMBERSTRING_LENGTH; i++) {
    if (n & (1 << i)) { str[ NUMBERSTRING_LENGTH-1-i]='1'; }
    else { str[ NUMBERSTRING_LENGTH-1-i]='0'; }
  }
  str[ NUMBERSTRING_LENGTH]='\0';

}

START

7. Übungsaufgaben

Es gibt für diese Vorlesung keine explizite Übungsaufgabe; eine solche wird in der kommenden VL 'Grundlagen der Informatik' gestellt werden im Zusammenhang mit dem Stoff über digitale Schaltungen.

START