Tutorial

Boolsche Algebra und Rechnen im Dualsystem

von

Seite 1 von 1

Logisch rechnen für Anfänger

Ich will euch hier mal ein kleines, einfaches Tutorial für logisches, binäres Rechnen geben. Hoffe, es hilft euch, einige Dinge kompakter und effektiver umzusetzen.

Zuerst einmal zum Unterschied zwischen den einzelnen Rechensystemen.
Jeder von euch wird das "dezimale" Rechensystem aus der Schule kennen.
Dabei stellt eine Stelle den Wertebereich von 0 bis 9 dar. Wenn man zu einer einstelligen Zahl eine 1 addiert, vergrössert sich der Wert solange, bis ein Maximum der Stelle erreicht wurde, und ein Übertrag stattfinden muss.
9 + 1 = 10
Jetzt hat man eine neue Stelle erzeugt, welche ebenfalls wieder das Maximum erreichen muss, um eine weitere Stelle zu erzeugen
99 + 1 = 100
usw.

Im Vergleich zum binären Rechensystem, kann eine Stelle nur den Wertebereich von 0 bis 1 darstellen. Sollte also zu dem Wert 1 eine 1 addiert werden, findet sofort ein Übertrag statt.
1 + 1 = 10
Addiert man nun zum Maximum der beiden Stellen wieder eine 1, entsteht wieder ein Übertrag.
11 + 1 = 100
111 + 1 = 1000
usw.

Da ihr sicher das dezimale System kennt, brauche ich euch ja nicht erklären, wie man damit grossartig Rechenoperationen durchführt.
Daher beschränke ich mich mal auf das binäre System, und zeige die Beziehung der jeweiligen Zahl im binären System, zum dezimalen System auf.

Binär = Dezimal

   0 =  0

   1 =  1

  10 =  2

  11 =  3

 100 =  4

 101 =  5

 110 =  6

 111 =  7

1000 =  8

1001 =  9

1010 = 10

1011 = 11

1100 = 12

.........

Was kann man nun damit anfangen? .. nun .. "eigentlich" nicht sehr viel. Der Computer hingegen schon. Der arbeitet mit nichts anderem. Damit der Computer eure Zahl 10 und die Zahl 5 addieren kann, nutzt er sogenannte Verknüpfungsoperationen oder auch Logische-Operatoren.
Diese Operationen lauten:

OR = Oder

AND = Und

NOT = Nicht

...

Wie arbeiten diese Operatoren?
Wenn man sich ein Bit (1 oder 0) als Schalter vorstellt, dann kann man folgende Vergleiche ziehen:
A = Schalter-A
B = Schalter-B
L = Lampe

OR
Ein "OR" sagt aus, das EINE von beiden Variablen eine 1 sein kann, um eine 1 ausgeben zu können

A (aus) OR B (aus) ergibt L (aus)

A (ein) OR B (aus) ergibt L (ein)

A (aus) OR B (ein) ergibt L (ein)

A (ein) OR B (ein) ergibt L (ein)

Ürigens: Solch einen Vergleich nennt man auch "Wahrheitstabelle". Sie zeigt auf, was passiert, wenn man einen "Schalter" ein- oder ausschaltet.

AND
Ein "AND" sagt aus, dass BEIDE Variablen jeweils eine 1 haben müssen, um eine 1 zu erhalten.

A (aus) AND B (aus) ergibt L (aus)

A (ein) AND B (aus) ergibt L (aus)

A (aus) AND B (ein) ergibt L (aus)

A (ein) AND B (ein) ergibt L (ein)

NOT
Ein "NOT" sagt aus, dass der eingehende Zustand umgedreht ausgegeben wird.

A (aus) ergibt L (ein)

A (ein) ergibt L (aus)

...

NOR, XOR, ... sind Kombinationen aus diesen Grundbefehlen.
Mehr Gatter und passende Warheitstabelle: http://de.wikipedia.org/wiki/Logikgatter

Wie das ganze mit binären Zahlen aussieht, ist auch schnell gezeigt.

0 OR 0 = 0

0 OR 1 = 1

1 OR 0 = 1

1 OR 1 = 1

Was hat das mit meinem Computer zu tun?
Nun .. wie oben schon gesagt, rechnet der Computer ausschliesslich im binären System, (noch, aber das ist ein anderes Thema)...
Wenn ein Computer nun die Zahl 10 zu der Zahl 2 addieren will, dann muss er diese beiden binär umgewandelten Zahlen 1010 und 11 Logisch miteinander verknüpfen. Das macht der Computer mit einer simplen Addition.
1010 + 11 = 1101
Wie kommt das Ergebnis zustande? ... naja... Simple Addition halt ;) So wie man dezimal einen Übertrag erzeugt, macht das der Computer auch.

Was bringt mir das nun?
Gehen wir mal davon aus, ihr schreibt ein Spiel. Dieses Spiel hat ein quadratisches Spielfeld, auf dem Wände stehen können. Jede Wand repräsentiert eine 1; keine Wand eine 0.
Hat man nun ein Feld von 8x8 Pixel, dann wären das 8 * 8 = 64 Informationen.
Ein Weg wäre, jeweils eine 1 oder eine 0 in eine Datei zu schreiben.

Dim Feld(8, 8) as UInteger

Dim X as UInteger

Dim Y as UInteger

Dim D as String

For Y = 1 to 8

    For X = 1 to 8

        If Feld(Y, X) = 1 Then

            D = D & "1"

        Else

            D = D & "0"

        End If

    Next

Next

Dieses Beispiel geht alle 8 Felder Höhe mit jeweils 8 Felder Breit durch, und schreibt entsprechend dem Wert im Array eine 1 oder ein 0 in einen String.
Diesen kann man nun abspeichern. Man hat quasi eine "MAP" gespeichert. Jedes Byte steht nun in dieser Datei für eine Wand oder keine Wand.

Nun .. wie man aus dem Beispiel erkennen kann, werden nur 2 Werte-Typen gespeichert .. entweder eine 1 oder eine 0. Da wir sicher wissen, dass ein Byte 8 Bit besizt, könnten wir dies nun anwenden, um unsere MAP zu "komprimieren".
Wir speichern einfach nicht jede 1 oder jede 0 in einem separaten Byte, sondern in einem gemeinsamen Byte. Das bringt uns eine Ersparnis von 1:8 ein.

Damit dies funktioniert, müssen wir uns der LOGISCHEN Berechnung zuwenden.

Und wie machen wir das nun?
Unser Byte hat 8 Bits.

- - - - - - - -

Das heißt, wir haben 8 Punkte, auf welchen wir jeweils 8 Felder speichern können.
Wenn wir nun eine 1 oder eine 0 in unser Byte speichern möchten, müssen wir erstmal wissen, an welche Position dieser Wert soll.
Die Position wäre dann 0, 1, 2, 3, 4, ... 7.
Diese Position kann man errechnen, indem man 2 ^ (hoch) Position rechnet.

2^0 = 1 = -------X

2^1 = 2 = ------X-

2^2 = 4 = -----X--

2^3 = 8 = ----X---

usw.

PS: Man rechnet immer von rechts nach links.

So .. Wir möchten nun also an jeder Position einen Wert speichern. Das können wir simpel mit dem OR-Befehl machen, indem wir den Wert einfach hinein verknüpfen:

00000000 OR 00000001 = 00000001

oder

00000001 OR 00001000 = 00001001

Dim Feld(8, 8) as UInteger

Dim X as UInteger

Dim Y as UInteger

Dim B as UByte

Dim D as String

For Y = 1 to 8                       'Alle Zeilen durchgehen

    B = 0                            'Beim Beginn einer neuen Zeile Wert zurücksetzen

    For X = 1 to 8                   'Alle Felder einer Zeile durchgehen

        If Feld(Y, X) = 1 Then       'Ist das Feld eine Wand?

            B = B OR (2 ^ x)         'Die Adresse errechnen und mit den bereits gespeicherten Werten verknüpfen

        End If                       'Else brauchen wir nicht, da schon alle Bit-Positionen mit 0 gefüllt sind.

    Next

    D = D & Chr(B)                   'Nach jeder fertigen Zeile den ASCII-Code erzeugen, und im String speichern.

Next

Das hätten wir. Aber nun müssen wir ja auch die Werte wieder einlesen.
Dazu benötigen wir eine "BITMASKE"
Diese Bitmaske beinhaltet an der Position eine 1, die wir auslesen möchten.
z.B. haben wir den Wert 11001100 und möchten das 4te Bit auslesen. Dazu erzeugen wir eine Maske, die dieses Bit beinhaltet 00001000. Anschliessend verknüpfen wir unsere Maske mit dem Wert, und erhalten das Bit, das sich dort befindet.

11001100 AND 00001000 = 00001000

11001100 AND 00000100 = 00000100

11001100 AND 00000010 = 00000000

11001100 AND 00000001 = 00000000

Nachdem wir nun das gesuchte Bit extrahiert haben, können wir prüfen, ob das Bit an oder aus ist.
If 00001000 = 00001000 Then
Und damit wäre das Problem schon gelöst.

Dim Feld(8, 8) as UInteger

Dim X as UInteger

Dim Y as UInteger

Dim B as UByte

Dim M as UByte

For Y = 1 to 8                       'Alle Zeilen durchgehen

    B = Asc(Mid(D, Y, 1))            'Auslesen des Zeilen-Bytes

    For X = 1 to 8                   'Alle Felder eine Zeile durchgehen

        M = 2 ^ (X - 1)              'Maske erzeugen (-1) deshalb, weil wir mit 0 beginnen (siehe oben)

        If (B AND M) = M Then        'Ist das Bit aktiv?

            Feld(Y, X) = 1           '1 setzen

        End If                       'Else brauchen wir nicht, da schon alles mit 0 gefüllt ist.

    Next

Next

So .. Ich hoffe, das ich einigen von euch helfen konnte, und ihr nun mit dem Bit-Rechnen etwas vertrauter seid als vorher ;)

MfG
TPM

Zusätzliche Informationen und Funktionen

Das Tutorial wurde am 11.09.2009 von ThePuppetMaster angelegt.
Die aktuellste Version wurde am 11.09.2009 von ThePuppetMaster gespeichert.

Bearbeiten

Versionen