Vom Umgang mit Bits in AutoLisp, Teil 2

Eigentlich haben wir ja im vorigen Kapitel schon alles gelernt, was man über den Umgang mit Bits in AutoLisp wissen sollte. Trotzdem kommt hier noch ein Kapitel zu diesem Thema, denn es gibt da noch die Funktion (boole ...), an der sich schon viele AutoLisp-Einsteiger die Zähne ausgebissen haben. Die AutoLisp-Onlinehilfe hält sich zu diesem Thema allerdings auch sehr zurück: Wer nicht sowieso schon Bescheid weiss, wird aus der Hilfe sowieso nicht schlau.

Ich werde versuchen, dass Thema hier so anfängerfreundlich wie möglich zu erörtern. Es geht allerdings auch nicht ohne ein paar grundlegende Kenntnisse der Mathematik bzw. Logik - aber vielleicht reicht auch durchaus ein gewisses Vorstellungs- bzw. Abstraktionsvermögen. Wir werden sehen - und wer auch trotz meiner gut gemeinten Bemühungen hier nicht durchsteigt, der sei damit getröstet, dass man auch ohne diese Funktion gute Lisp-Programme schreiben kann. (boole ...) ist eine schöne Funktion für Programme, in denen komplexe Logik eine Rolle spielt. Aber meistens braucht man sie überhaupt nicht.

Die (boole)-Funktion bekommt immer drei Argumente. Das erste Argument ist eine Art Steuercode, es muss eine Zahl zwischen 0 und 15 sein. Die beiden anderen Argumente sind dann zwei Ganzzahlen, wie wir es schon von (logand) und (logior) kennen. Diese beiden Funktionen, die die Logik-Funktionen AND und OR repräsentieren, sind aber nur zwei Möglichkeiten, wie man zwei Zahlen bitweise miteinander verknüpfen kann.

Insgesamt existieren 16 solcher Möglichkeiten, und es wird nicht überraschen, dass der Steuercode von 0 bis 15 genau diese Möglichkeiten widerspiegelt. Um es gleich vorweg zu nehmen: AND hat den Code 1, und OR hat den Code 7. Wir vergleichen mit (logand) und (logior) und benutzen dazu unsere selbstdefinierte Funktion (prinbin) aus dem vorigen Kapitel, um die Bits wieder 'persönlich' inspizieren zu können:

(prinbin 170) =>
"00000000 00000000 00000000 10101010 : 170"

(prinbin 118) =>
"00000000 00000000 00000000 01110110 : 118"

(prinbin(logand 170 118)) =>
"00000000 00000000 00000000 00100010 : 34"

(prinbin(boole 1 170 118)) =>
"00000000 00000000 00000000 00100010 : 34"

(prinbin(logior 170 118)) =>
"00000000 00000000 00000000 11111110 : 254"

(prinbin(boole 7 170 118))
"00000000 00000000 00000000 11111110 : 254"

Wir sehen, dass (boole 1 ...) identisch mit (logand) ist, und dass (boole 7 ...) das selbe tut wie (logior). Bleibt also eigentlich nur noch zu klären, wozu die anderen 14 Steuercodes gut sein sollen. Aber das ist nicht so ganz einfach... Untersuchen wir doch mal den Steuercode 2 (die uninteressanten Aufrufe von (prinbin) lasse ich jetzt einfach weg):

"00000000 00000000 00000000 10101010 : 170"
"00000000 00000000 00000000 01110110 : 118"

(prinbin(boole 2 170 118)) =>
"00000000 00000000 00000000 10001000 : 136"

Es scheint so, als würden hier Bits gesetzt, wenn in der ersten Zahl eine 1 vorliegt, in der zweiten aber eine 0. Eine kleine Gegenprobe scheint das zu bestätigen:

(prinbin(boole 2 170 255)) =>
"00000000 00000000 00000000 00000000 : 0"

Es ist so, und wir können den Zusammenhang doch einmal etwas mehr auf den Punkt bringen: Wenn wir das Bit der ersten Zahl immer als A bezeichnen und das zweite mit B, dann haben wir hier den Fall A AND not B. Das kürzen wir dann noch ein bisschen ab, in dem wir es so schreiben: A AND ~B.

Wir könnten jetzt auf die Idee kommen, vielleicht den Steuercode 0 zu untersuchen, oder auch den Code 3. Die Untersuchungen zu Code 0 sparen wir uns hier - denn (boole 0 ... ...) gibt immer die Zahl 0 als Ergebnis zurück. Das mag für Theoretiker hochinteressant sein, aber nicht für uns. Aber auf den Steuercode 3 können wir doch mal ein Auge riskieren:

"00000000 00000000 00000000 10101010 : 170"
"00000000 00000000 00000000 01110110 : 118"

(prinbin(boole 3 170 118)) =>
"00000000 00000000 00000000 10101010 : 170"

Hmmm, das bringt uns erst einmal nicht viel weiter... Vielleicht lag's an den Zahlen? Wir versuchen es einfach mal mit zwei anderen Zahlen:

"00000000 00010011 00110000 10110101 : 1257653"
"00000000 01100101 01001011 10111000 : 6638520"

(prinbin(boole 3 1257653 6638520)) =>
"00000000 00010011 00110000 10110101 : 1257653"

Nicht besonders aufregend, oder? Wir bekommen immer A zurück. Aber die Ursache ist schnell aufgeklärt: Steuercode 3 ist einfach die Kombination von Code 1 und Code 2, denn auch hier wird binär gearbeitet. Tatsächlich kennt (boole) nur die Codes 0, 1, 2, 4 und 8. Alle anderen Steuercodes sind Kombinationen. Wenn wir das Ergebnis ein wenig näher untersuchen, können wir folgende Wahrheitstafeln aufstellen:

A B | (A AND B)    A B | (A AND ~B)
----+----------    ----+---------
0 0 |     0        0 0 |     0
0 1 |     0        0 1 |     0
1 0 |     0        1 0 |     1
1 1 |     1        1 1 |     0

(A AND B)(A AND ~B)|(A AND B) OR (A AND ~B)
-------------------+-----------------------
    0        0     |           0
    0        0     |           0
    0        1     |           1
    1        0     |           1

Natürlich herrscht hier doch noch ein wenig Erklärungsbedarf, insbesondere darüber, woher das OR kommt, das die Ergebnisse der Steuercodes 1 und 2 verknüpft. Tja, ich habe es einfach hingeschrieben, und wer sich die untere Wahrheitstafel in Ruhe anschaut, wird feststellen, dass auch gar nichts anderes dort hineinpassen würde!

Jetzt muss es sein: Den Ausdruck '(A AND B) OR (A AND ~B)' kann man umformen - er wird zu 'A AND (B OR ~B)'. Streng nach den Regeln der Prädikatenlogik betrachtet, haben wir hier das Distributivgesetz angewendet. Interpretieren wir den Teil '(B OR ~B)', was irgendwie doch recht starke und durchaus berechtigte Assoziationen zu Shakespeare erweckt, was aber wiederum überhaupt nichts mit dem zu tun hat, was die Philosophen unter dem Assoziativgesetz (ja, die Prädikatenlogik ist eher eine Domäne der Philosophie als der Mathematik)...

Ich fange lieber noch mal von vorne an: B ODER NICHT B bedeutet einfach: Es ist völlig Wurst, was mit B ist. Nur A zählt, und das haben wir ja von Anfang an gewusst! Nach dem Absorptionsgesetz können wir jetzt den Ausdruck rigoros auf 'A' zusammenstreichen:

(A AND B) OR (A AND ~B) ; Originalausdruck
A AND (B OR ~B)         ; Distributivgesetz
A                       ; Absorptionsgesetz

Den Steuercode 3 können wir uns also dahin tun, wo sich auch schon der Code befindet: Uninteressant. Schauen wir uns lieber den Code 4 an, jetzt allerdings in verkürzter Darstellung meinerseits:

"00000000 00010011 00110000 10110101 : 1257653"
"00000000 01100101 01001011 10111000 : 6638520"

(prinbin(boole 4 1257653 6638520)) =>
"00000000 01100100 01001011 00001000 : 6572808"

Da wir nun schon echte Meister im Erkennen binärer Zusammenhänge sind, sehen wir sofort, dass hier der Fall '~A AND B' vorliegt, Steuercode 2 spiegelverkehrt sozusagen. Code 5 ist dann (logischerweise) '(A AND B) OR (~A AND B)', was wir ruckzuck unter Anwendung von Distributiv- und Absorptionsgesetz zu 'B' und sonst gar nichts zusammenstauchen. Ein kurzer Test zeigt, dass das zu Recht geschah:

(prinbin(boole 5 1257653 6638520)) =>
"00000000 01100101 01001011 10111000 : 6638520"

Fall 6 stellt sich nun so dar: Da es sich hier um die Kombination von 2 und 4 handelt, haben wir es mit dem Ausdruck '(A AND ~B) OR (~A AND B)' zu tun. Hier stellt sich eine echte Überraschung ein: Wir können das nicht kürzen, aber es ist wirklich eine interessante Kombination! Hier handelt es sich nämlich um das Entweder-Oder, mit dem wir bisher noch gar nichts zu tun hatten. Dieses XOR spielt übrigens in der Praxis eine genausogrosse Rolle wie AND und OR.

Wer sich einmal die (entget)-Liste, die Geometriedaten also, eines ACIS-3D-Solids in AutoCAD angeschaut hat, war sicherlich verwundert über den offensichtlichen Datenmüll. AutoDESK verschlüsselt diese Daten, offensichtlich aus lizenzrechtlichen Gründen. Die XOR-Funktion wird seit jeher für eine primitive Verschlüsselung verwendet, die den Vor- bzw. Nachteil (je nach Standpunkt des Verschlüsselers oder desjenigen, der den Schlüssel knacken möchte) hat, dass eine zweite XOR-Anwendung die Verschlüsselung wieder aufhebt. Eine kurze Praxiseinlage:

"00000000 00010011 00110000 10110101 : 1257653"
"00000000 01100101 01001011 10111000 : 6638520"

(prinbin(boole 6 1257653 6638520)) =>
"00000000 01110110 01111011 00001101 : 7764749"

; die Rückentschlüsselung:
(prinbin(boole 6 7764749 6638520)) =>
"00000000 00010011 00110000 10110101 : 1257653"

; und noch eine:
(prinbin(boole 6 1257653 7764749)) =>
"00000000 01100101 01001011 10111000 : 6638520"

An dieser Stelle wird auch klar, dass die Reihenfolge der beiden letzten Argumente, der Zahlen also, bei manchen Steuercodes eine Rolle spielt, bei anderen aber nicht. Bei Code 6 spielt es jedenfalls keine Rolle, ob wir die Zahlen vertauschen - ebensowenig wie bei 0 oder 1. Bei zwei bzw. 4 ist das anders: Ein Tausch der Argumente macht aus Code 2 den Code 4 und umgekehrt.

Kommen wir nun zum komplizierten Fall 7, von dem wir ja schon wissen, dass es sich um das OR handelt. Die Kombination von 1, 2 und 4 ergibt folgenden Ausdruck: '(A AND ~B) OR (~A AND B) OR (A AND B)'. In Worten heisst das: Entweder A, aber nicht B, oder auch nicht A, aber B, oder auch sowohl A als auch B. Diese umständliche Formulierung ergibt sich aus der internen Logik der (boole)-Funktion, und sie lässt sich ohne Bedenken zu '(A OR B)' umformen. Den Beweis bleibe ich allerdings einfach schuldig...

Wer bisher noch nicht 'ausgestiegen' ist, hat nun allen Grund dazu: Die zweite Hälfte mit den Codes 8 bis 15 wird noch wesentlich unangenehmer! Code 8 ist für das WEDER-NOCH zuständig, das in der Praxis auch sehr nützlich ist. Allerdings kommt hier ein unangenehmes Detail ins Spiel: Wir testen den Code 8 einfach mal:

"00000000 00010011 00110000 10110101 : 1257653"
"00000000 01100101 01001011 10111000 : 6638520"

(prinbin(boole 8 1257653 6638520)) =>
"11111111 10001000 10000100 01000010 : -7830462"

Wie man sieht, ist das Ergebnis eine negative Zahl! Das 'unangenehme Detail' nennt sich übrigens 'Zweierkomplement' und bezeichnet die Art und Weise, wie negative Ganzzahlen im Rechner verarbeitet werden. Um etwas Einblick zu gewinnen, lassen wir uns die Zahlen 2, 1, 0, -1, -2, -3 binär ausgeben:

"00000000 00000000 00000000 00000010 :  2"
"00000000 00000000 00000000 00000001 :  1"
"00000000 00000000 00000000 00000000 :  0"
"11111111 11111111 11111111 11111111 : -1"
"11111111 11111111 11111111 11111110 : -2"
"11111111 11111111 11111111 11111101 : -3"

Ein paar Erklärungen: Negativ sind Zahlen dann, wenn das höchstwertige Bit gesetzt ist, also das ganz linke, oder - da wir heutzutage mit 32-Bit-Systemen arbeiten, das 32. Bit von rechts. Würde man die Sache so handhaben, dass man dieses Bit als Vorzeichenbit verwendet und die anderen 31 Bit immer identisch als Werte-Bits, dann hätten wir diesen Fall:

; so sieht es in Wirklichkeit nicht aus!
"0 0000000 00000000 00000000 00000010 : + 2"
"0 0000000 00000000 00000000 00000001 : + 1"
"0 0000000 00000000 00000000 00000000 : + 0"
"1 0000000 00000000 00000000 00000000 : - 0 "
"1 0000000 00000000 00000000 00000001 : - 1 "
"1 0000000 00000000 00000000 00000010 : - 2 "

Nun, da sind zwei Nullen drin! Es gibt aber kein +0 oder -0, die Null ist immer vorzeichenlos. Das würde jeden Prozessor völlig durcheinanderbringen! Es muss also korrigiert werden:

; und so auch nicht - nur ein Modell!
"0 0000000 00000000 00000000 00000010 : + 2"
"0 0000000 00000000 00000000 00000001 : + 1"
"0 0000000 00000000 00000000 00000000 : + 0"
"1 0000000 00000000 00000000 00000000 : - 1 "
"1 0000000 00000000 00000000 00000001 : - 2 "
"1 0000000 00000000 00000000 00000010 : - 3 "

So stellt sich zwar eine unschöne Asymmetrie ein, aber die muss man zugunsten der eindeutigen Null in Kauf nehmen. Die Realität sieht aber noch anders aus: In der Zweierkomplement-Darstellung werden alle Bits negiert. Hier noch einmal, wie es tatsächlich gehandhabt wird:

"00000000 00000000 00000000 00000010 :  2"
"00000000 00000000 00000000 00000001 :  1"
"00000000 00000000 00000000 00000000 :  0"
"11111111 11111111 11111111 11111111 : -1"
"11111111 11111111 11111111 11111110 : -2"
"11111111 11111111 11111111 11111101 : -3"

Diese Darstellungsweise hat gegüber den beiden letzten Modellen den Vorteil, dass der Prozessor bei Additionen keine Rücksicht darauf nehmen muss, ob eine negative oder positive Zahl vorliegt - der Rechenweg bleibt der Gleiche! Mehr möchte ich zum Thema Zweierkomplement jetzt auch nicht mehr sagen - dieses Kapitelist sowieso schon zu lang!

Noch einmal zurück zur (boole)-Funktion: Das NOR (Weder-Noch) setzt also da ein Bit, wo weder A noch B eines haben. Bei zwei positiven Zahlen, die ja beide eine Null als MSB (most significant bit, das linke also) haben, führt das zwangsläufig zu einem negativen Ergebnis.

Wir sollten jetzt aber doch noch einmal etwas systematischer an die (boole)-Funktion herangehen. Alle sechzehn Möglichkeiten dieser Funktion lassen sich in einer großen Wahrheitstafel darstellen - un plötzlichwird alles ganz einfach und logisch. In der AutoLisp-Hilfe finden wir ja schon einen Ansatz von Dokumentation, nämlich eine kleine Wahrheitstafel für die (boole)-Funktion selbst:

Int1 Int2 | Operator bit
 0    0   |      8
 0    1   |      4
 1    0   |      2
 1    1   |      1

Was uns noch fehlt, ist nur ein Ansatz, wie diese kleine Tabelle zu interpretieren ist: Es handelt sich einfach um eine Aufschlüsselung, wann was negiert wird. Code 1 negiert also nichts, Code 2 negiert die Bits in Zahl 2, Code 4 in Zahl 1 und Code 8 in beiden. Mit diesem Wissen ausgestattet, sehen wir nun, dass die große Wahrheitstafel ganz einfach aufgebaut ist.

Nicht notwendig, aber vielleicht für den einen oder anderen ganz nützlich ist das Wissen um die 'wissenschaftlichen Namen', um die ich die Tabelle erweitert habe. Ich erwähne diese also nur für alle Fälle...

A     0 0 1 1
B     0 1 0 1
-------------

0     0 0 0 0     Nullfunktion

1     0 0 0 1     Konjunktion (A AND B)

2     0 0 1 0     2. Inhibition (A AND ~B)

3     0 0 1 1     1. Identität (A)

4     0 1 0 0     1. Inhibition (~A AND B)

5     0 1 0 1     2. Identität (B)

6     0 1 1 0     Antivalenz (A >-< B) = (A XOR B)
                            = ((~A AND B) OR (A AND ~B))

7     0 1 1 1     Disjunktion (A OR B)

8     1 0 0 0     Peirce-Funktion (A NOR B) = ~(A OR B)

9     1 0 0 1     Äquivalenz (A <=> B)

10    1 0 1 0     2. Negation (~B)

11    1 0 1 1     2. Implikation (A OR ~B)

12    1 1 0 0     1. Negation (~A)

13    1 1 0 1     1. Implikation (~A OR B)

14    1 1 1 0     Sheffer-Funktion (A NAND B) = ~(A AND B)

15    1 1 1 1     Einsfunktion

Leider konnte (und wollte) ich das hier nicht zu wissenschaftlich betreiben. Insbesondere bei der verwendung von Zeichen war ich auf das beschränkt, was sich als ASCII-Text darstellen lässt. Das Ganze noch als Grafik darzustellen, erschien mir dann doch zu viel des Guten. Ich denke aber, dass es auch trotz kleiner formaler Mängel seinen Zweck erfüllt.

Wer tapfer bis hierher durchgehalten hat und nun meint, er könne endlich aufatmen: Nein. Dieses Thema geht weiter! Die (boole)-Funktion ist enträtselt, aber zum Handwerkszeug eines AutoLisp-Programmierers gehört auch eine Portion Wissen im Zusammenhang mit der Logik. Das Distributiv- oder auch das Absorptionsgesetz lassen sich nämlich z.B. auch auf verschachtelte (if(and(not....(or...(not...-Ausdrücke anwenden, und die DeMorganschen Regeln halte ich da für geradezu unverzichtbar! Und ist es nicht ein verlockendes Ziel, aus einem seitenlangen Wust von ifs und ands und ors im Handumdrehen eine kleine, übersichtliche Funktion machen zu können?

Techniken wie das Karnaugh-Veitch-Diagramm machen das möglich. Ob sich dieses Kapitel dann hier anschliessen wird oder auf die Fortgeschrittenen-Seiten wandert, werde ich erst entscheiden, wenn es fertig ist.