Aufgabe zu Zahlenmengen

[herrSchlaumann]

Hallo zusammen,

meine Aufgabe ist es, eine Klasse Set zu implementieren, die Mengen von Zahlen zwischen 0 und 31 verwaltet. Dazu soll als Datenstruktur ne int-Zahl benutzt werden, die als Bitfolge interpretiert wird. Die Zahl 44 kann z.B. als Menge (2, 3, 5) aufgefasst werden. Es sollen Operationen zum Einfügen und Entfernen von Elementen sowie zum Vereinigen von Mengen und zur Berechnung der Schnittmenge zweier Mengen.

Hier der Code der Musterlösung:

//Sets of integers between 0 and 31
class Set {
    int set = 0;

    void include(int x) {
        if (x >= 0 && x < 32) set |= 1 << x;
    }

    void exclude(int x) {
        if (x >= 0 && x < 32) set &= ~(1 << x);
    }

    boolean contains(int x) {
        return x >= 0 && x < 32 && ((1 << x) & set) != 0;
    }

    void union(Set s) {
        set |= s.set;
    }

    void intersect(Set s) {
        set &= s.set;
    }

    public String toString() {
        StringBuilder b = new StringBuilder();
        boolean first = true;
        b.append("{");
        for (int i = 0; i < 32; i++)
            if (contains(i)) {
                if (first) first = false; else b.append(",");
                b.append(i);
            }
        b.append("}");
        return b.toString();
    }
}

public class Kap11A01 {

    public static void main(String args[]) {
        Set s = new Set();
        s.include(35);
        s.include(5);
        Out.println("s = " + s);

        Set s1 = new Set();
        s1.include(5);
        s1.include(6);
        s1.include(10);
        s.union(s1);
        Out.println("s = " + s);

        s1 = new Set();
        s1.include(3);
        s1.include(10);
        s.intersect(s1);
        Out.println("s = " + s);

        s.exclude(10);
        Out.println("s = " + s);
    }
}

Ich tue mich super schwer damit, das zu verstehen..
1.

void include(int x) {
        if (x >= 0 && x < 32) set |= 1 << x;

Was passiert da mit den Shift-Operatoren?

2.

public String toString() {
        StringBuilder b = new StringBuilder();
        boolean first = true;
        b.append("{");
        for (int i = 0; i < 32; i++)
            if (contains(i)) {
                if (first) first = false; else b.append(",");
                b.append(i);
            }
        b.append("}");
        return b.toString();

Hier bin ich völlig raus. Alleine die Methode contains() lässt mich nur mit Fragezeichen zurück.
Könnt ihr mir da erklären, was da im Programm passiert?

Besten Dank!

 

[Xyz1]

Was passiert da mit den Shift-Operatoren?

Eins wird um x Stellen nach links verschoben, danach wird die x. Stelle auf 1 gesetzt, durch die Veroderrung.

Alles möchte ich eigentlich nicht erklären....

 

[JStein52]

Dann sag ich noch was zu contains: das prüft ob das x-te Bit in der Variablen set auf 1 gesetzt ist

 

[Meniskusschaden]

Die Menge wird durch die Variable set repräsentiert, die gemäß Aufgabenstellung als Bitfolge interpretiert werden soll. Die Zahl n ist in der Menge enthalten, falls Bit n von Set gesetzt ist. Beispielsweise ist Drei enthalten, falls Bit 3 (also das vierte von rechts) gesetzt ist. Wenn man 1 binär um drei Stellen nach links verschiebt, erhält man den dezimalen Wert, der dem Wert dieses Bits entspricht, nämlich 8. Deshalb taucht das Muster 1 << x immer wieder auf.
Die verschiedenen anderen Operationen dienen dann dazu, das entsprechende Bit in Set zu setzen, zu löschen oder abzufragen. Du solltest dich also mit den Operatoren zur Bitmanipulation beschäftigen.