11.12 Die Klasse BitSet für Bitmengen

Die Klasse BitSet bietet komfortable Möglichkeiten zur bitweisen Manipulation von Daten. Das Datum kann beliebig groß sein, und über Methoden von BitSet lassen sich die einzelnen Bits leicht ändern. Zudem lassen sich Bits wie in einem Vektor hinzufügen und das Objekt verwaltet selbstständig die Größe. Ein leeres BitSet wird mit dem Standard-Konstruktor angelegt. Ein weiterer Konstruktor erlaubt eine Startgröße, die ein Vergrößern aufschiebt.

11.12.1 Ein BitSet anlegen und füllen

Jedes Bit an einer Position besitzt zwei Zustände: gesetzt oder nicht gesetzt. Dies bringt es in die Nähe der booleschen Werte, die ebenso zwei Zustände besitzen. Mit zwei Methoden lassen sich die Bits des BitSet leicht ändern: set(bitNummer) und clear(bitNummer). Da der Bit-Container automatisch wächst, ist es problemlos möglich, in einem BitSet-Exemplar mit 100 Bits das Bit 300 zu setzen. Das Objekt wird automatisch mit 200 Null-Bits aufgefüllt, bevor das Bit 300 gesetzt wird.

Über die Methode size() erfahren wir, wie viele Bits das Objekt umfasst. Spannender ist die Methode length(). Sie liefert die Position des höchsten gesetzten Bits. In size() werden überzählige führende Null-Bits mitgezählt, ähnlich wie ungenutzte Array-Elemente im capacity()-Wert eines Vektors. Die Abfrage, ob ein Bit gesetzt ist, erfolgt mit der Methode get(bitNummer). Sie gibt true zurück, falls das Bit gesetzt ist, andernfalls false.

Hier klicken, um das Bild zu Vergrößern

BitSet bs = new BitSet();
bs.set( 0 );
bs.set( 2 );

11.12.2 Mengenorientierte Operationen

Das BitSet erlaubt mengenorientierte Operationen mit einer weiteren Menge. Jedes Bit der im Parameter übergebenen Menge wird mit dem Objekt in einer bestimmten Weise verknüpft. Das Ergebnis der Operation wird dem aktuellen Objekt zugewiesen. Drei Operationen sind verfügbar: Die Oder-Operation setzt das Bit, falls es im Objekt gesetzt ist oder das Bit im zweiten BitSet gesetzt ist. Die Und-Operation setzt das Bit, falls es im Objekt gesetzt ist und das Bit im zweiten BitSet gesetzt ist. Die Xor-Operation setzt das Bit, falls es nur in einem der beiden Objekte gesetzt ist. Damit werden die Operationen Mengenvereinigung, Durchschnitt und symmetrischer Durchschnitt implementiert.

11.12.3 Funktionsübersicht

Die Funktionen von BitSet sind überschaubar. Leider existieren keine Methoden, die Bits aus anderen Quellen, etwa einem Bitfeld aus byte[], übernehmen und einfügen. Da BitSet nicht final ist, können wir diese Zusatzfunktionalität in einer Unterklasse realisieren.

class java.util.BitSet
implements Cloneable, Serializable

BitSet() Erzeugt ein neues BitSet-Objekt.

BitSet( int nbits ) Erzeugt ein BitSet mit der vorgegebenen Größe von nbits. Alle Bits sind am Anfang auf false gesetzt. Ist die Größe kleiner null, so wird eine NegativeArraySizeException ausgelöst.

void andNot( BitSet set ) Löscht alle Bits im Bitset, die dort set gesetzt sind.

boolean clear() Löscht den Container.

void set( int bitIndex ), clear( int bitIndex ) Setzt oder löscht ein Bit. Ist der Index negativ, wird eine IndexOutOfBoundsException ausgelöst.6

void set( int bitIndex, boolen value ) Setzt den Wahrheitswert value an die Stelle bitIndex.

void set( int fromIndex, int toIndex ), clear( int fromIndex, int toIndex ) Setzt oder löscht Bits im ausgewiesenen Bereich.

void set( int fromIndex, int toIndex, boolen value ) Setzt den Wahrheitswert value im ausgewählten Bereich.

boolen equals( Object o ) Vergleicht sich mit einem anderen BitSet-Objekt o.

boolean get( int bitIndex ) Liefert den Wert des Bits am übergebenen Index. Kann bei negativem Index wieder eine IndexOutOfBoundsException auslösen.

BitSet get( int fromIndex, int toIndex ) Liefert ein neues BitSet-Objekt mit den ausgewählten Bits.

void and( BitSet set ), void or( BitSet set ), void xor( BitSet set ) Verknüpft dieses BitSet-Exemplar per Und-, Oder-, Xor-Operation mit dem angegebenen BitSet-Objekt.

boolen isEmpty() Liefert true, wenn keine Bits gesetzt sind.

Implementierungsdetails

Um die Geschwindigkeit zu optimieren, wurden die Methoden der Klasse BitSet nicht synchronisiert. Greift also ein Thread auf die Daten zu, während ein anderer modifiziert, kann es zu möglichen Inkonsistenzen kommen. Intern werden die Bitsets in einem long-Array abgelegt.

11.12.4 Primzahlen in einem BitSet verwalten

Das folgende Programm zeigt die Anwendung der Klasse BitSet am Beispiel der Konstruktion der Menge von Primzahlen. Jedes gesetzte Bit entspricht einer Primzahl. In diesem Fall ist der Einsatz der Klasse BitSet angebracht, da eine Zahl in einem Wertebereich nur eine Primzahl oder keine sein kann.

Listing 11.13 Primtest.java

import java.util.*;
class Primtest
{
  final static int MAXPRIM = 30;
   public static void main( String args[] )
  {
    BitSet b = new BitSet();
     for ( int i = 2; i <= MAXPRIM; i++ )
    {
      boolean ok = true;
       for ( int j = 2; j < i; j++ )
        if ( b.get(j) && (i % j) == 0 ) {
          ok = false;
          break;
        }
       if ( ok )
        b.set( i );
    }
     for ( int i = 1; i <= MAXPRIM; i++ )
      if ( b.get(i) )
        System.out.println( i );
  }
}