--- title: 'Die Klasse BitSet für Bitmengen' url: 'https://www.tutego.de/blog/javainsel/2013/06/die-klasse-bitset-fr-bitmengen' markdown: 'https://www.tutego.de/blog/javainsel/2013/06/die-klasse-bitset-fr-bitmengen.md' date: '2013-06-05' description: 'Die Klasse BitSet ist eine platzsparende und performante Alternative zu boolean-Arrays und bietet komfortable Möglichkeiten zur bitweisen Manipulation von Daten. Beliebig viele Bits lassen sich wie in anderen dynamischen Datenstrukturen hinzufügen und verwalten. Die Methoden von BitSet lesen und mo…' taxonomy: category: - Insel - 'Java 8' --- # Die Klasse BitSet für Bitmengen ![Illustration einer tropischen Insel mit Palmen und einem hohen Berg](https://www.tutego.de/blog/javainsel/user/themes/tutego/images/insel-cover.jpg)# Java Blog für Programmierer [Java Blog für Programmierer](https://www.tutego.de/blog/javainsel/) ## Die Klasse BitSet für Bitmengen 05.06.2013 · [Christian Ullenboom](https://www.tutego.de/blog/javainsel/author/admin/) Die Klasse BitSet ist eine platzsparende und performante Alternative zu boolean-`Arrays` und bietet komfortable Möglichkeiten zur bitweisen Manipulation von Daten. Beliebig viele Bits lassen sich wie in anderen dynamischen Datenstrukturen hinzufügen und verwalten. Die Methoden von BitSet lesen und modifizieren die einzelnen Bits leicht und führen Mengenoperationen durch. Auch wenn der Klassenname auf „`Set`“ endet, ist BitSet keine Implementierung der `Set`-Schnittstelle und sogar ein ein bisschen irreführend, da ein `Set` Elemente nur einmal enthalten kann, in BitSet aber natürlich beliebig viele Nullen und Einsen vorkommen können, in dem die Reihenfolge auch eine elementare Rolle spielt. **Ein BitSet anlegen** Ein leeres BitSet wird mit dem Standard-Konstruktor angelegt. Ein weiterer Konstruktor erlaubt eine Startgröße, die ein Vergrößern der internen Datenstruktur aufschiebt. 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. Weiterhin gibt es die statischen Methoden BitSet `valueOf`(long\[\])/valueOf(byte\[\])/valueOf(ByteBuffer)/valueOf(LongBuffer) um Bit-Mengen aus anderen Quellen zu importieren. Es exportieren dann das BitSet mit `toByteArray()` in ein byte\[\] und `toLongArray()` in ein long\[\]. ##### **BitSet füllen und Zustände erfragen** 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(bitPosition)` und `clear(bitPosition)`. Da der Bit-Container automatisch wachsen kann, ist es problemlos möglich, in einem BitSet-Exemplar mit 100 Bit das Bit 300 zu setzen. Das Objekt wird automatisch mit 200 `false`-Bits aufgefüllt, bevor das Bit 300 gesetzt wird. Die Abfrage, ob ein Bit gesetzt ist, erfolgt mit der Methode `get(bitPosition)`. Sie gibt `true` zurück, falls das Bit gesetzt ist, andernfalls `false`. Beispiel: Setze in einem BitSet das erste und das dritte Bit: ```java BitSet bs = new BitSet(); bs.set( 0 ); bs.set( 2 ); System.out.println( bs.get(0) ); // true System.out.println( bs.get(1) ); // false System.out.println( bs.nextSetBit(1) ); // 2 ``` class `java.util.BitSet`implements Cloneable, Serializable - `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 set(int bitIndex)` - `clear(int bitIndex)`Setzt oder löscht ein Bit. Ist der Index negativ, wird eine `IndexOutOfBoundsException` ausgelöst. - `void set(int bitIndex, boolean 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, boolean value)`Setzt den Wahrheitswert value im ausgewählten Bereich. - `void flip(int bitIndex)`Setzt das Bit an der Stelle `bitIndex` auf das Komplement. Aus `true` wird `false`, und aus `false` wird `true`. - `void flip(int fromIndex, int toIndex)`Setzt alle Bits im gegebenen Bereich auf das Komplement. - `int nextSetBit(int fromIndex)/previousSetBit(int fromIndex)` - `int nextClearBit(int fromIndex)/previousClearBit(int fromIndex)`Liefert den Index des nächsen/vorangenden als `true` bzw. `false` gesetzten Bits ab `fromIndex`. Gibt es keine Position, ist die Rückgabe –1. Der Index ist inklusiv. ##### **Mengenorientierte Operationen** Das BitSet erlaubt mengenorientierte Operationen wie Und, Oder, Xor mit einem weiteren BitSet, etwa in der Methode `and(BitSet)`. Jedes Bit des übergebenen BitSet wird mit dem aktuellen Objekt in einer bestimmten Weise verknüpft. Das Ergebnis der Operation wird dem aktuellen Objekt zugewiesen. Wichtige Operationen sind: - Die Oder-Operation setzt das Bit, falls es im eigenen BitSet oder im zweiten BitSet gesetzt ist. - Die Und-Operation setzt das Bit, falls es im eigenen Objekt und im zweiten BitSet gesetzt ist. - Die Xor-Operation setzt das Bit, falls es nur in einem der beiden BitSet-Objekte gesetzt ist. Die Operationen bilden die Basis für die Mengenvereinigung, den Durchschnitt und den symmetrischen Durchschnitt. class `java.util.BitSet`implements Cloneable, Serializable - `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. - `void andNot(BitSet set)`Löscht alle Bits im aktuellen BitSet, deren korrespondierendes Bit in set gesetzt ist. - `boolean intersects(BitSet set)`Liefert `true`, wenn das eigene BitSet die gleichen gesetzten Bits wie set hat. ##### **Weitere Methoden von BitSet** Über die Methode `size()` erfahren wir, wie viele Bits das BitSet zur internen Speicherung der Werte nutzt.[\[1\]](file:C:/Users/Christian/Dropbox/Insel/2/#_ftn1_2765) Die Methode `length()` liefert die Position des höchsten gesetzten Bits. Die Anzahl aller gesetzten Bits liefert `cardinality()`. Beispiel Methoden `size()`, `length()` und `cardinality()` im Vergleich: ```java BitSet bs = BitSet.valueOf( new byte[]{ 0b011001 } ); System.out.println( bs.size() ); // 64 System.out.println( bs.length() ); // 5 System.out.println( bs.cardinality() ); // 3 ``` Die sonstigen Methoden von BitSet sind überschaubar. class `java.util.BitSet`implements Cloneable, Serializable - `int size()`Liefert den Platzbedarf in Bits für dieses BitSet. - `int cardinality()`Liefert die Anzahl der Bits, die `true` sind. - `int length()`Liefert die „Größe“ des BitSet, also den Index des höchsten gesetzten Bits. - `boolean clear()`Leert den Container, indem alle Bits auf `false` gesetzt werden. - `boolean isEmpty()`Liefert `true`, wenn keine Bits gesetzt sind. - `boolean equals(Object o)`Vergleicht sich mit einem anderen BitSet-Objekt o. - `IntStream stream()`Liefert einen `Stream` der Indexe mit gesetzten Bit, vom niedridsten zum höchsten. Beispiel: Gib alle Postionen gesetzter Bytes aus und prüfe, ob auf allen greaden Indexen das Bit gesetzt ist: ```java boolean b = BitSet.valueOf( new byte[]{ 0b1010 } ).stream() .peek( System.out::println ) .allMatch( i -> (i & 1) == 1 ); ``` Die Ausgabe wird hier sein: 1, 3. **Implementierungsdetails** Intern legt die Implementierung von BitSet die Bit-Sammlungen in einem long-Array ab. Um die Geschwindigkeit zu optimieren, sind 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. --- [\[1\]](file:C:/Users/Christian/Dropbox/Insel/2/#_ftnref1_2765) Es ist vergleichbar mit dem `capacity()`-Wert eines Vektors. Kategorien: [Insel](https://www.tutego.de/blog/javainsel/category/insel/), [Java 8](https://www.tutego.de/blog/javainsel/category/java-8/) ## 2 Kommentare **Christian Ullenboom** · [01.03.2020 13:19](#comment-750436) · [Antwort auf einen Kommentar](#comment-728945) Danke, korrigiert: boolean intersects(BitSet set) Liefert true, wenn diese BitSet und set mindestens an einer Postion ein gemeinsames gesetztes Bit haben. **Oliver Scharmann** · [08.10.2019 09:58](#comment-728945) Bei der Methode boolean intersects(BitSet set) hat sich ein kleiner Fehler eingeschlichen. Die Methode liefert true zurück, wenn mindestens ein Bit existiert, welches in beiden Bitsets auf true gesetzt ist. Anders formuliert kann man auch sagen, dass das Ergebnis true ist, wenn die Schnittmenge der auf true gesetzten Bits beider Bitsets nicht leer ist. Die bisherigen Kommentare wurden aus WordPress übernommen. Neue Kommentare sind derzeit geschlossen. [← Alle Beiträge](https://www.tutego.de/blog/javainsel/) --- ## Navigation - Previous: [Thema der Woche: Parallele Versionen im Versionsverwaltungssystem führen](https://www.tutego.de/blog/javainsel/2013/06/thema-der-woche-parallele-versionen-im-versionsverwaltungssystem-fhren.md) - Next: [Mehrere Zufallszahlen generieren, Stream in Random](https://www.tutego.de/blog/javainsel/2013/06/mehrere-zufallszahlen-generieren-stream-in-random.md)