ein Kapitel zurück                                           ein Kapitel weiter

Im Laufe des Kurses haben sie schon oft Code-Abschnitte gesehen in denen wir Überprüfen ob ein Bit gesetzt war oder nicht. Oder wir haben es eben gesetzt oder gelöscht. Nun, C bietet zwar keine solche Funktionen an, aber wir können uns das ganze mit ein paar Macros selbst zusammenbasteln.

Hauptsächlich werde Bit-Arrays eingesetzt bei....

  • bei Datenstrukturen die ein Bit-Array enthalten
  • den aktuellen Status eines Zustandes überprüfen (Bit gesetzt, gelöscht)
  • den aktuellen Status eines Zustandes ändern in dem ein Bit gesetzt wird


Nun ein theoretisches Anwendungsbeispiel wie sie Bit-Array managen können.

Wir verwenden als Datentypen unsigned char womit uns (meist) garantiert wird das alle Bits in einem Byte unterkommen.

(Anmerkung: Laut ANSI-C muss ein char mindestens 1 Byte gross sein)

Wir verwenden hier typedef, somit können wir eventuelle Anpassungen auf einen anderen Datentypen später in dieser Zeile vornehmen...... 

typedef unsigned char BIT_TYPE;

Als nächstes benötigen wir einen Datentypen der die Anzahl der Bits im Array enthält......... 

#define BIT_NBIT (CHAR_BIT * sizeof(BIT_TYPE))

Mit diesem werden wir auch im Laufe des Codes weiterarbeiten. CHAR_BIT ist in der Headerdatei <limits.h> definiert und gibt die Anzahl der Bits in einem Byte an. Diese Defination war ist nötig, sollten wir andere Datentypen verwenden außer unsigned char.

Nun benötigen wir ein Macro in dem wir die Anzahl der BIT_TYPE Elemente festlegen die wir benötigen um N Bits zu verwenden........ 

#define BIT_SIZE(N) (((N) + BIT_NBIT-1) / BIT_NBIT)

Nun könnten wir schon ein Bit-Array wie folgt definieren......... 

BIT_TYPE bit_array[BIT_SIZE(SIZE)];

Hier zu das ganze in einem kurzem Codeabschnitt....... 

/*Download:bitarr.c*/

#include <stdio.h>
#include <limits.h>
#define ONE_BYTE 8
#define TWO_BYTE 16

typedef unsigned char BIT_TYPE;
#define BIT_NBIT (CHAR_BIT * sizeof(BIT_TYPE))
#define BIT_SIZE(N) (((N) + BIT_NBIT-1) / BIT_NBIT)

int main()
{

 BIT_TYPE bit_array[BIT_SIZE(ONE_BYTE)]={
0};
 BIT_TYPE bit_array2[BIT_SIZE(TWO_BYTE)]={
0};

 printf("bit_array ist %d Bytes gross\n",sizeof(bit_array));
 printf("bit_array2 ist %d Bytes gross\n",sizeof(bit_array2));
 return 0;
}

Das macht natürlich noch keinen Sinn und dient nur dazu das sie ein wenig Gefühl für das Thema bekommen. Nun benötigen wir noch ein Makro für den Index wieviele Elemente von BIT_TYPE vorhanden sind...... 

#define BIT_ELNUM(N) ((N) / BIT_NBIT)

Ein weiteres Makro wäre.... 

#define BIT_NUM(N) ((N) % BIT_NBIT)

Damit stellen wir fest welches Bit in BIT_TYPE Bit N beinhaltet. Nun haben wir alle Makros, damit wir einzelne Bits setzen, löschen und abfragen können.

Bit setzen....... 

#define BIT_SET(bit_array, N) \
        ((bit_array)[BIT_ELNUM(N)] |= (BIT_TYPE)1 << BIT_NUM(N))

N-te Bit in Bitarray setzen.

Bit löschen...... 

#define BIT_CLEAR(bit_array, N) \
        ((bit_array)[BIT_ELNUM(N)] &= ~((BIT_TYPE)1 << BIT_NUM(N)))

N-te Bit in Bitarray löschen.

Auf Bit testen..... 

#define BIT_TEST(bit_array, N) \
        ((bit_array)[BIT_ELNUM(N)]& ((BIT_TYPE)1 << BIT_NUM(N)))

N-te Bit in Bitarray testen ob gesetzt.

Dazu jetzt zu unserem Finalen Programm das das ganze Demonstriert....

/*Download:bitarr2.c*/

#include <stdio.h>
#include <limits.h>
#define SEVEN_BIT 7


typedef unsigned char BIT_TYPE;
#define BIT_NBIT (CHAR_BIT * sizeof(BIT_TYPE))
#define BIT_SIZE(N) (((N) + BIT_NBIT-1) / BIT_NBIT)

#define BIT_ELNUM(N) ((N)/BIT_NBIT)
#define BIT_NUM(N) ((N) % BIT_NBIT)

#define BIT_ZERO(bit_array, N)\
        memset(bit_array,0,BIT_SIZE(N)*sizeof(BIT_TYPE))

#define BIT_SET(bit_array, N) \
        ((bit_array)[BIT_ELNUM(N)] |= (BIT_TYPE)1 << BIT_NUM(N))
#define BIT_CLEAR(bit_array, N) \
        ((bit_array)[BIT_ELNUM(N)] &= ~((BIT_TYPE)1 << BIT_NUM(N)))
#define BIT_TEST(bit_array, N) \
        ((bit_array)[BIT_ELNUM(N)]& ((BIT_TYPE)1 << BIT_NUM(N)))

/*Alle Bits auf 1 setzen*/
void setall(BIT_TYPE *b)
{

 int i;
 for(i=0; i<SEVEN_BIT; i++)
  if(BIT_SET(b,i))
    printf("Bit %d gesetzt\n",i+1);
  else
    printf("Bit %d nicht gesetzt\n",i+1);
}


int main()
{

 BIT_TYPE bit_array[BIT_SIZE(SEVEN_BIT)];
 int i;

 /*Alle Bits mit 0 initialisieren*/
 BIT_ZERO(bit_array, SEVEN_BIT);

 /*Testen ob wir Bit 4 gesetzt wurde*/
 if(BIT_TEST(bit_array, 3))
  printf("Bit 4 ist bereits gesetzt\n");
 else
  printf("Bit 4 ist noch nicht gesetzt\n");

 /*Jetzt setzen wir Bit 3 und überprüfen das gleich*/
 if(BIT_SET(bit_array, 3))
   if(BIT_TEST(bit_array, 3))
     printf("Bit 4 wurde gesetzt\n");
   else
     printf("Bit 4 konnte nicht gesetzt werden\n");

 printf("Momentane Bitdarstellung : ");
 for(i=0; i<SEVEN_BIT; i++)
   printf("%d",BIT_TEST(bit_array,i) ?1 :0);
 printf("\n");

 /*Bit 4 wieder löschen und ausgeben*/
 BIT_CLEAR(bit_array, 3);
  printf("Momentane Bitdarstellung (Nach BIT_CLEAR) : ");
 for(i=0; i<SEVEN_BIT; i++)
   printf("%d",BIT_TEST(bit_array,i) ?1 :0);
 printf("\n");

 /*Funktion mit der wir alle Bits auf 1 setzen*/
 setall(bit_array);
 /*Zur überprüfung*/
 printf("Momentane Bitdarstellung (Nach setall) : ");
 for(i=0; i<SEVEN_BIT; i++)
   printf("%d",BIT_TEST(bit_array,i) ?1 :0);
 printf("\n");

 /*Alle Bits wieder löschen*/
 BIT_ZERO(bit_array, SEVEN_BIT);
 /*und...*/
 printf("Momentane Bitdarstellung (Nach BIT_ZERO) : ");
 for(i=0; i<SEVEN_BIT; i++)
   printf("%d",BIT_TEST(bit_array,i) ?1 :0);
 printf("\n");

 return 0;
}

Hinzugekommen ist hier nach das Makro BIT_ZERO, womit alle einzelnen Bits auf 0 gesetzt werden. Weiterhin haben wir hier noch ein Funktion setall() geschrieben die alle Bits auf 1 stellt. Dies hätten wir zwar auch in ein Makro packen können aber hier halt mal anders. Der Quellcode dürfte auch ausreichend kommentiert sein. Probieren sie ruhig an den Quellcode herum.

Was hier noch fehlen dürfte wäre ein Makro zum dynamischen reservieren von Speicher und um das ganze auch wieder freizugegeben. Die Makros will ich euch nicht vorenthalten....... 

#define BIT_MALLOC(N)\
        ((BIT_TYPE *)malloc(BIT_SIZE(N) * sizeof(BIT_TYPE)))
#define BIT_FREE(bit_array) free(bit_array)

Somit können sie in der main-Funktion folgendermaßen Speicher für das Bit-Array reservieren........ 

BIT_TYPE *bitarray;

if(( bitarray = BIT_MALLOC(size)) == NULL)
 { /*Fehler bei malloc*/ }
else
 { /*Erfolgreich size Speicher alloziert*/ }

Zugegegben ich habe das Thema nur Angeschnitten, aber in meisten Büchern wird das erst gar nicht erwähnt.

ein Kapitel zurück          nach oben           ein Kapitel weiter


© 2001,2002 Jürgen Wolf