14.5 Die Klasse BitSet

• 14.5 Die Klasse BitSet
  • 14.5.1 Elementweise Operationen
  • 14.5.2 Mengenorientierte Operationen

Die Klasse BitSet dient dazu, Mengen ganzer Zahlen zu repräsentieren. Sie erlaubt es, Zahlen einzufügen oder zu löschen und zu testen, ob bestimmte Werte in der Menge enthalten sind. Die Klasse bietet zudem die Möglichkeit, Teil- und Vereinigungsmengen zu bilden.

Ein BitSet erlaubt aber auch noch eine andere Interpretation. Sie kann nämlich auch als eine Menge von Bits, die entweder gesetzt oder nicht gesetzt sein können, angesehen werden. In diesem Fall entspricht das Einfügen eines Elements dem Setzen eines Bits, das Entfernen dem Löschen und die Vereinigungs- und Schnittmengenoperationen den logischen ODER- bzw. UND-Operationen.

Tip

Diese Analogie wird insbesondere dann deutlich, wenn man eine Menge von ganzen Zahlen in der Form repräsentiert, daß in einem booleschen Array das Element an Position i genau dann auf true gesetzt wird, wenn die Zahl i Element der repräsentierten Menge ist. Mit BitSet bietet Java nun eine Klasse, die sowohl als Liste von Bits als auch als Menge von Ganzzahlen angesehen werden kann.

14.5.1 Elementweise Operationen

Ein neues Objekt der Klasse BitSet kann mit dem parameterlosen Konstruktor angelegt werden. Die dadurch repräsentierte Menge ist zunächst leer.

public BitSet()

java.util.BitSet

Das Einfügen einer Zahl (bzw. das Setzen eines Bits) erfolgt mit Hilfe der Methode set. Das Entfernen einer Zahl (bzw. das Löschen eines Bits) erfolgt mit der Methode clear. Die Abfrage, ob eine Zahl in der Menge enthalten ist (bzw. die Abfrage des Zustands eines bestimmten Bits), erfolgt mit Hilfe der Methode get:

public void set(int bit) public void clear(int bit) public boolean get(int bit)

java.util.BitSet

14.5.2 Mengenorientierte Operationen

Die mengenorientierten Operationen benötigen zwei Mengen als Argumente, nämlich das aktuelle Objekt und eine weitere Menge, die als Parameter übergeben wird. Das Ergebnis der Operation wird dem aktuellen Objekt zugewiesen. Das Bilden der Vereinigungsmenge (bzw. die bitweise ODER-Operation) erfolgt durch Aufruf der Methode or, das Bilden der Durchschnittsmenge (bzw. die bitweise UND-Operation) mit Hilfe von and. Zusätzlich gibt es die Methode xor, die ein bitweises Exklusiv-ODER durchführt. Deren mengentheoretisches Äquivalent ist die Vereinigung von Schnittmenge und Schnittmenge der Umkehrmengen.

Seit dem JDK 1.2 gibt es zusätzlich die Methode andNot, mit der die Bits der Ursprungsmenge gelöscht werden, deren korrespondierendes Bit in der Argumentmenge gesetzt ist.

JDK1.1-1.3

public void or(BitSet set) public void and(BitSet set) public void xor(BitSet set) public void andNot(BitSet set)

java.util.BitSet

Das folgende Programm verdeutlicht die Anwendung der Klasse BitSet am Beispiel der Konstruktion der Menge der Primzahlen kleiner gleich 20. Dabei werden besagte Primzahlen einfach als Menge X der natürlichen Zahlen bis 20 angesehen, bei der jedes Element keinen echten Teiler in X enthält:

001 /* Listing1404.java */ 002 003 import java.util.*; 004 005 public class Listing1404 006 { 007 private final static int MAXNUM = 20; 008 009 public static void main(String[] args) 010 { 011 BitSet b; 012 boolean ok; 013 014 System.out.println("Die Primzahlen <= " + MAXNUM + ":"); 015 b = new BitSet(); 016 for (int i = 2; i <= MAXNUM; ++i) { 017 ok = true; 018 for (int j = 2; j < i; ++j) { 019 if (b.get(j) && i % j == 0) { 020 ok = false; 021 break; 022 } 023 } 024 if (ok) { 025 b.set(i); 026 } 027 } 028 for (int i = 1; i <= MAXNUM; ++i) { 029 if (b.get(i)) { 030 System.out.println(" " + i); 031 } 032 } 033 } 034 }

Listing1404.java

Listing 14.4: Konstruktion von Primzahlen mit der Klasse BitSet

Die Ausgabe des Programms ist:

Die Primzahlen <= 20:
  2
  3
  5
  7
  11
  13
  17
  19