Datum: 14.04.2008, 22:26 - Autor: Manko10

Ein Tutorial etwas anderer Art steht an. Hier geht es nicht direkt um das Programmieren, sondern mehr um reine Logik (wobei der Übergang zwischen beiden Begrifflichkeiten ja fließend ist ). Und da keine sprachspezifischen Dinge erläutert werden, liegt dieses Tutorial in der Kategorie Sonstiges.

1. Einführung

Worum geht es? Genau wie der Titel schon sagt: um das Realisieren einer Rechtevergabe mithilfe boolescher Algebra.

Nehmen wir das Beispiel eines Forums. Jedes Unterforum hat eine eindeutige ID-Nummer, anhand der es identifiziert wird.
Jetzt wollen wir für jede Benutzergruppe festlegen, welche Unterforen sichtbar sind und welche nicht. Natürlich könnte man für jedes sichtbare Forum die ID speichern. Etwa so:

Code:
1: 2: 3: 4: 5: 6: Tabelle `groups`: +------+--------+------------------+ | `id` | `name` | `visible_forums` | +------+--------+------------------+ | 1 | User | 1|3|7|4|12|2 | +------+--------+------------------+

Ein wenig unpraktisch, oder? Man muss für jedes Forum die ID speichern. Man kann es sich aber auch einfacher machen und an dieser Stelle bloß die Zahl 4254 speichern. In ihr ist alles gespeichert, was man wissen muss.

Nur wie bin ich auf diese Zahl gekommen? Um das zu verstehen, muss man ein wenig über boolesche Algebra und bitweise Operatoren wissen (nein, ich werde jetzt nichts über George Boole erzählen, wer mehr über den guten Mann wissen will, der benutze bitte die Wikipedia - auch kann ich keine komplette Einführung in die boolesche Algebra bieten, sondern nur ein paar grundlegendste Grundlagen der Basis aller Anfänge).

2. Boolesche Algebra und bitweise Operatoren

Zuerst einmal nehmen wir uns das bitweise UND und das bitweise ODER vor.
Mit dem bitweisen UND kann man gezielt Bits ausschalten. Dazu nehmen wir zwei Ganzzahlen und verknüpfen sie durch den UND-Operator auf Bitebene:

Code:
1: 2: 3: 4: 5: 6: Bitweises UND: 10011001011101 & 10011011100110 ---------------- = 10011001000100

Wie kommt es zu dem Ergebnis? Der UND-Operator & schaltet im Ergebnis immer ein Bit an (1), wenn in beiden zu vergleichenden Zahlen dieses Bit ebenfalls gesetzt ist. Ist an der Stelle jedoch nur ein oder kein Bit gesetzt, steht im Ergebnis an dieser Stelle eine 0.
Das ist wie in der Programmierung das logische UND. Das Ergebnis ist nur wahr, wenn beide zu vergleichenden Ausdrücke wahr sind. Ist eines oder keines wahr, so ist das ganze Ergebnis unwahr.

Der nächste Operator ist das bitweise ODER. Hiermit können Bits gezielt eingeschaltet werden:

Code:
1: 2: 3: 4: 5: 6: Bitweises ODER: 10011001011101 | 10011011100110 ---------------- = 10011011111111

Im Gegensatz zum UND-Operator werden hier die Bits eingeschaltet, wenn das Bit in mindestens einer Zahl gesetzt ist. Also auch vergleichbar mit dem logischen ODER. Es muss mindestens ein Ausdruck war sein, damit das gesamte Gebilde wahr ist.

Der nächste und für dieses Tutorial letzte Operator, den ich vorstelle, ist der Shift-Operator. Mit seiner Hilfe lassen sich Bits verschieben.
Dabei gibt es den Left-Shift-Operator und den Right-Shift-Operator. Wie die Namen schon sagen, lassen sich damit die Bits nach links oder nach rechts verschieben und zwar um n Stellen.

Hier ein Beispiel:

Code:
1: 2: 3: 4: 5: Bitweise Linksverschiebung um 2 Stellen: 10011001011101 << 2 ----------------------- = 1001100101110100

Die Bits werden um zwei Stellen nach links verschoben. Dabei wird rechts mit Nullen aufgefüllt. De facto entspricht jede Stelle Verschiebung einer Multiplikation mit 2 (in diesem Falle also 2 * 2).

Der Right-Shift-Operator arbeitet ähnlich, nur dass er die Bits nach rechts verschiebt (das entspricht etwa einer Division durch 2):

Code:
1: 2: 3: 4: 5: Bitweise Rechtsverschiebung um 2 Stellen: 10011001011101 >> 2 --------------------- = 100110010111

3. Es geht los!

So, das sind die Grundlagen. Jetzt können wir mit der Berechnung der Zahl anfangen, die ich zu Anfang des Tutorials einfach so in den Raum geworfen habe.
Dazu bilden wir Zweierpotenzen. Die Rechnung sieht wie folgt aus:

Code:
1: 2^n * b

n steht dabei für die ID des Forums und b für einen booleschen Zustand (1 oder 0), der angibt, ob das jeweilige Forum sichtbar ist.
Diese Rechnung führen wir für jedes Forum durch. Die einzelnen Ergebnisse werden dabei addiert.

Hinweis: Da wir der Einfachheit halber nicht alle Foren in die Rechnung einbeziehen, sondern nur die, die auch sichtbar sein sollen, spare ich mir die Multiplikation mit b, da b immer 1 wäre.

Code:
1: 2: 3: 4: 5: 6: 7: 8: 2^1 = 2 2^3 = 8 2^7 = 128 2^4 = 16 2^12 = 4096 2^2 = 4 ----------- Summe: 4254

Und heraus kommt... na, wer hätte das gedacht? Die Zahl, die ich eingangs erwähnte. Mit dieser Zahl ist nun festgehalten, welche Foren diese User-Gruppe sehen kann und welche nicht.

4. Zurückrechnen

Jetzt stellt sich nur noch die Frage, wie man diese Zahl wieder zurückrechnen kann.
Dazu benötigen wir die Bit-Operatoren, die ich vorhin eingeführt habe. Jedoch nicht alle, sondern nur das bitweise UND und die bitweise Linksverschiebung (Left-Shift).

Zuerst müssen wir die Bits der Zahl 1 um n Stellen nach links verschieben. Doch wie viel sind n Stellen? Ganz einfach. n steht auch hier wieder für die ID des zu prüfenden Forums. Als Beispiel dient das Forum mit der ID 4.
Also eine Rechnung wie folgt:

Code:
1: 2: 3: 4: 1 << 4 -------- = 16 (dezimal) = 10000 (binär)

Du wunderst dich, dass ich keine Dualzahlen mehr genommen habe? Das habe ich ganz einfach deshalb nicht mehr getan, da du in der Programmierung die Bit-Operatoren wohl eher mit Dezimalzahlen benutzen wirst.

Im nächsten Schritt benutzen wir den UND-Operator. Als Operanden dienen dabei die errechnete Zahl 4254 und das Ergebnis der letzten Rechnung:

Code:
1: 2: 3: 4: 4254 & 16 ----------- = 16 (dezimal) = 10000 (binär)

Wie du siehst, hat sich im Ergebnis nichts geändert. Wie kommt's? Sehen wir uns die beiden Operanden mal in binärform an:

Code:
1: 2: 3: 4: 1000010011110 (4254) & 10000 (16) --------------- = 10000

Das Ergebnis ist größer als 0, da ein Bit eingeschaltet ist.

Probieren wir dies jetzt einmal mit einer Forums-ID aus, die nicht in der Foren-Liste enthalten ist: der Fünf.

Code:
1: 2: 3: 4: 5: 6: 7: 8: 9: 1 << 5 -------- = 32 (dezimal) = 100000 (binär) 4254 & 32 ----------- = 0 (dezimal) = 0 (binär)

Plötzlich werden alle Bits ausgeschaltet. Warum? Schauen wir uns die Operanden wieder in binärform an:

Code:
1: 2: 3: 4: 1000010011110 (4254) & 100000 (32) --------------- = 000000

Die Bits passen nirgendwo aufeinander, das Ergebnis ist unwahr (0).

Somit haben wir die Formel gefunden, mit der sich errechnen lässt, ob der User das Forum sehen darf, oder nicht (n steht wieder für die Forums-ID und x für die zurückzurechnende Zahl):

Code:
1: Forum sichtbar = ((x & (1 << n)) > 0)

Dieser boolesche Ausdruck definiert nun, ob das Forum sichtbar ist. Ist das Ergebnis der Berechnung nämlich größer als 0, so darf der User das Forum sehen. Andernfalls nicht.

1:

Forum sichtbar = (((x & (1 << 31)) * (x & (1 << 2))) > 0)

Kommentar schreiben:

Ihre Blog-Website wird nicht gefordert. Bitte füllen Sie das Feld nicht aus:

Titel (optional):

Name (optional):

Kommentar: