Titel | Inhalt | Suchen | Index | DOC | Handbuch der Java-Programmierung, 3. Auflage
<< | < | > | >> | API | Kapitel 14 - Collections I

## 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.4

    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

Titel | Inhalt | Suchen | Index | DOC | Handbuch der Java-Programmierung, 3. Auflage, Addison Wesley, Version 3.0
<< | < | > | >> | API | © 1998-2002 Guido Krüger, http://www.javabuch.de