Programmieren mit C++

Bitvektoren sind wie ein Array von Flags einzusetzen. Ein Flag kann den Wert 0 (nicht gesetzt) oder 1 (gesetzt) annehmen. Die Sprache C bietet jedoch keinen Datentyp Bit. Für die einzelnen Bits eines Bytes sind zwar Operationen vorhanden, sie können getrennt angesprochen werden, der kleinste integrale Datentyp ist aber das Byte. Auch ein Byte kann die Werte 0 und 1 annehmen. Für ein Flag aber ein Byte vorzusehen, bedeutet eine Platzverschwendung um den Faktor 8. In C++ bietet es sich deshalb an, eine Klasse für Bitvektoren zu erstellen, die diesen Nachteil nicht hat. In der Klasse wird für jedes Flag nur ein Bit verwendet. Für das Setzen und Löschen der Flags sowie für das Abfragen des Zustands der Flags sind Funktionen bzw. Operatoren definiert.

Array von Flags

Die Größe der Bitvektoren ist variabel. Sie kann beim Anlegen des Objekts (Konstruktor) angegeben werden oder beim Verwenden eines Konstruktors ohne Dimensionierung durch eine Memberfunktion festgelegt werden. Die Klasse allokiert für den Bitvektor nur so viel Speicher, wie benötigt wird. Die Dimensionierung des Bitvektors durch eine Memberfunktion ist unter gewissen Umständen notwendig. Verwenden Sie den Bitvektor innerhalb einer anderen Klasse, so kann nur diese Version eingesetzt werden.

Folgende Konstruktion ist nicht zulässig:

Variable Größe

class test 
{
    private:
        Bitvektor    vektor(200);
 
    public:
        .
}

Die Konstruktorversion mit der Angabe der Dimensionierung ist nicht möglich. Es geht aber so:

Unzulässige Konstruktion

class test 
{
    private:
        Bitvektor    vektor;
 
    public:
        .
}

Da die Konstruktorversion ohne Dimensionierung möglich ist, kann die Dimensionierung des Bitvektors jetzt im Konstruktor der Klasse test durchgeführt werden.

Zulässige Konstruktion

Die Klasse Bitvektor ist in der Headerdatei BITVEC.H definiert. Die privaten Variablen beinhalten den Zeiger auf den allokierten Speicherbereich, der die Bitmap beinhaltet, und die Angabe der Größe der Bitmap. Diese Größe beinhaltet die Anzahl der Bits, nicht der allokierten Bytes.

Headerdatei

Als Memberfunktionen existieren

• drei Konstruktoren

Konstruktor ohne Parameter

Konstruktor mit Größendimensionierung

Kopierkonstruktor

• Destruktor
• Funktion holeGroesse, die die Anzahl der Bits des Bitvektors zurückgibt.
• Funktion setzeGroesse, die oben beschriebene Funktion, die in Verbindung mit dem Konstruktor ohne Parameter eingesetzt werden muß.

Memberfunktionen

Die Funktionen setzeBit und loescheBit setzen bzw. löschen ein Bit. Ihnen muß als Parameter die Nummer des Bits übergeben werden (beginnend mit 0). Die Funktion istBitGesetzt liefert ein boolesches Ergebnis (0 oder 1), je nachdem, ob das Bit, dessen Nummer der Funktion als Parameter übergeben wird, gelöscht oder gesetzt ist. Der Operator [] gestattet die Programmierung mit Indizes, wie von Arrays gewohnt. Allerdings gibt es bei den Bitvektoren eine Einschränkung. Auf der linken Seite des Zuweisungszeichens ist der Operator zwar syntaktisch zulässig, aber er funktioniert nicht (mehr dazu bei der Beschreibung der Operatorfunktion). Der Operator = erlaubt die Zuweisung von Bitvektoren. Hierbei wird der Zielbitvektor eine Kopie des Quellbitvektors.

Bits bearbeiten

Der Quellcode befindet sich in der Datei BITVEC.CPP.

Quellcode

Der Konstruktor ohne Parameter legt keinen Bitvektor an. Er ist nur in Verbindung mit der Memberfunktion setzeGroesse oder mit dem Zuweisungsoperator sinnvoll, da mit einer leeren Bitmap nicht viel anzufangen ist. Die beiden Klassenvariablen groesse und p_vektor werden innerhalb des Konstruktors initialisiert, so daß erkennbar ist, daß das Objekt noch keine Bitmap beinhaltet.

Konstruktor ohne Parameter

Der Konstruktor mit dem Integerparameter legt einen Bitvektor an. Die Größe des Bitvektors in Bits entspricht dem Parameter. Der Speicher für den Bitvektor wird allokiert. Der Bitvektor ist mit gelöschten Bits initialisiert. Die Variable groesse enthält die Anzahl der Bits, die der Bitvektor beinhaltet, und die Variable p_vektor zeigt auf den Beginn des Speicherbereichs.

Konstruktor mit Integerparameter

Der Kopierkonstruktor benötigt als Parameter eine Referenz auf einen Bitvektor. Dieser Bitvektor wird in das anzulegende Objekt dupliziert. Es werden sowohl die Größe des Vektors als auch die Bits (gesetzt oder gelöscht) übernommen.

Kopierkonstruktor

Der Destruktor bringt die Speicherverwaltung in Ordnung. Wurde von dem Objekt Speicher allokiert, so gibt ihn der Destruktor wieder frei. Da der Destruktor immer aufgerufen wird, muß man sich um diese Probleme der Speicherverwaltung beim Verwenden der Klasse Bitvektor nicht mehr kümmern, sondern kann diese Arbeit dem Compiler überlassen.

Destruktor

int Bitvektor::holeGroesse(void)

holeGroesse gibt die Größe des Bitvektors in Bits zurück. Ist kein Bitvektor allokiert, was beim Verwenden des Konstruktors ohne Parameter und ohne zwischenzeitlichen Aufruf der Memberfunktion setze Größe oder einer Zuweisung geschehen kann, so liefert diese Funktion den Wert -1.

Memberfunktion holeGroesse

int Bitvektor::setzeGroesse(int anzahl)

setzeGroesse allokiert Speicher für den Bitvektor und initialisiert ihn mit gelöschten Bits. Die Funktion benötigt als Parameter die Anzahl der Bits des Vektors. Das Ergebnis ist ein Fehlercode. Ist er -1, so verfügt das Objekt bereits über allokierten Speicher. Diese Funktion ist nur in Verbindung mit dem Konstruktor ohne Parameter sinnvoll.

Memberfunktion setzeGroesse

int Bitvektor::setzeBit(int bit)

Mit setzeBit ist es möglich, ein Bit des Bitvektors zu setzen. Es wird das Bit gesetzt, dessen Nummer (beginnend mit 0) der Funktion als Parameter übergeben wird. Die Funktion liefert einen Fehlercode. Ist für dieses Objekt noch kein Speicher allokiert oder ist das Bit nicht im erlaubten Bereich, so kehrt die Funktion mit -1 zurück. Kann das Bit gesetzt werden, so liefert die Funktion das Ergebnis 0. Zum Setzen des Bits ist etwas Bitarithmetik notwendig, damit die anderen Bits im Byte nicht beeinflußt werden.

Memberfunktion setzeBit

int Bitvektor::loescheBit(int bit)

loescheBit ist analog zur Funktion setzeBit. Die Memberfunktion löscht das entsprechende Bit im Bitvektor.

Memberfunktion loescheBit

int Bitvektor::istBitGesetzt(int bit)

Die Funktion istBitGesetzt der Klasse Bitvektor liefert ein boolesches Ergebnis, kombiniert mit einem Fehlercode, was in C gleichbedeutend mit dem Datentyp int ist. Ist das Bit, dessen Nummer als Parameter übergeben wird, gesetzt, so liefert die Funktion 1, ist es gelöscht, so liefert die Funktion 0. Ist für dieses Objekt noch kein Speicher für die Bitmap allokiert oder ist das Bit außerhalb des zulässigen Bereichs, so ist das Funktionsergebnis -1.

Memberfunktion istBitGesetzt

Der Operator [] wird in C und auch in C++ für die Array-Indizierung eingesetzt. Da der Bitvektor ein Array von Bits ist, ist der Operator auch für diese Klasse sinnvoll (statt setzeBit, löscheBit oder istBitGesetzt). So kann statt

vektor.setzeBit(1);

auch

vektor[1] = 1;

programmiert werden. Die anderen korrespondierenden Funktionsaufrufe sind

vektor.loescheBit(1);
vektor[1] = 0;

und

if(vektor.istBitGesetzt(1) == 1)
if(vektor[1] == 1)

Soweit zur Theorie. Der Operator [] müßte als Funktionsergebnis eine Referenz auf den Datentyp liefern, um ihn auf beiden Seiten des Zuweisungsoperators verwenden zu können. Bei der Anweisung

vektor[1] = 0;

Operator []

ermittelt der Compiler die Adresse von vektor[1] als Adresse eines Bits und weist dem Inhalt dieser Adresse den Wert 0 zu. In C++ gibt es den Datentyp bit aber nicht. Somit ist dies nicht möglich. In der vorliegenden Version ist das Funktionsergebnis eine Referenz des Typs int. So viel Speicherplatz soll aber für ein Flag nicht verschwendet werden, da sonst statt des Bitvektors gleich ein Array von Integerwerten verwendet werden könnte. Würde die obige Zuweisung funktionieren, so würden 16 Flags statt des einen gelöscht. Dies verhindert aber die Operatorfunktion. Es wird nur eine statische Variable verändert. Das gewünschte Bit wird allerdings nicht geändert.

Die andere Art des Aufrufes,

ergebnis = vektor[1];

oder

if(vektor[1] == 0)

funktioniert. Auch hier wäre eigentlich eine Referenz auf ein Bit notwendig. Aber mit der Referenz auf den Integerwert funktioniert die Sache. Die statische Integervariable ergebnis wird auf 1 oder 0 gesetzt, je nachdem, ob das gewünschte Bit gesetzt oder gelöscht ist. Die Funktion gibt dann die Referenz auf diese Integervariable zurück. So wäre es eigentlich fast sinnvoller, diese Operatorfunktion nicht in die Klasse aufzunehmen, da sie in Verbindung mit einem lvalue nicht funktioniert. Ist man sich dessen bei der Programmierung bewußt, so kann man sie wenigstens auf der rechten Seite des Zuweisungsoperators verwenden, was doch leichter lesbare Programme ergibt.

Kein Datentyp bit

Der Zuweisungsoperator gestattet die Zuweisung kompletter Bitvektoren. Als Parameter benötigt die Funktion eine Referenz auf einen Bitvektor. Als Ergebnis liefert sie eine Referenz auf den eigenen Bitvektor. Dies ist für mehrfache Zuweisungen erforderlich:

vektor1 = vektor2 = vektor3;

Das Funktionsergebnis der Zuweisung vektor2 = vektor3 ist die Referenz auf vektor2, was für die nächste Zuweisungsfunktion benötigt wird.

Verfügt das Objekt bereits über eine Bitmap, so wird sie vernichtet (der Speicher wird freigegeben). Eine Bitmap der Größe des zuzuweisenden Operators wird allokiert, und die Bits werden einzeln übernommen.

Demonstrationsprogramm

Operator =

Um die Handhabung der Klasse zu verdeutlichen, ist in der Datei DEMOBIT.CPP ein Beispielprogramm enthalten.

Die Größe der Bitvektoren wird mit der Konstanten ANZAHL_BITS definiert. Das Makro ANZEIGE erledigt die Anzeige aller Bits eines Bitvektors. Ihm müssen als Parameter der Vektor und die Anzahl der Bits des Vektors übergeben werden.

Das Demonstrationsprogramm zeigt die Anwendung der Funktionen der Klasse Bitvektor. Zuerst wird der Vektor vektor1 ohne Größenangabe deklariert. Die Dimensionierung findet mit dem folgenden Funktionsaufruf statt. Anschließend ist der Bitvektor vektor2 definiert. Er beinhaltet eine Kopie des ersten Vektors. Nach dem Setzen aller Bits des ersten Vektors werden die beiden Vektoren angezeigt. Hier sieht man, daß der zweite Vektor eine Kopie des ersten Vektors ist. Die Änderungen des ersten Vektors sind im zweiten Vektor nicht durchgeführt. Der jetzt deklarierte Bitvektor vektor3 ist eine Kopie des ersten Bitvektors. Im ersten Bitvektor wird ab dem ersten Bit jedes dritte Bit gelöscht. Dann erfolgt die Anzeige des ersten und des dritten Vektors. Im dritten Vektor wird jedes zweite Bit gelöscht und dieser angezeigt. Das letzte Bit des dritten Bitvektors wird angezeigt, wobei auf das Bit mit der Funktion Operator [] zugegriffen wird. Dieser Zugriff funktioniert. Das folgende Setzen des ersten Bits des dritten Vektors mit der Funktion Operator [] funktioniert nicht, wie oben ausführlich erläutert wurde. Der Bitvektor vektor3 wird dem Bitvektor vektor2 zugewiesen und zuletzt der Bitvektor vektor2 angezeigt. Diese Ausgabe ist identisch zur zuvor erfolgten Ausgabe von vektor3, was aufgrund der Zuweisung auch zu erwarten ist.

DEMOBIT.CPP