XOR

Einführung

• Kürzlich hatte ich Gelegenheit, den XOR-Operator zu erklären. Früher war es unverzichtbar, XOR für Bitmanipulationen auf niedriger Ebene in Computern zu lernen, heute ist es für High-Level-Programmierer eher optional.
• Bei der Vorbereitung eines Vortrags über XOR habe ich verschiedene Gedanken dazu geordnet und beschlossen, sie schriftlich festzuhalten.

Die boolesche Logik von XOR

Was ist XOR?

• XOR ist ein logischer Operator, der zwei Bits als Eingabe erhält und ein Bit als Ausgabe liefert.
• Die Funktionsweise von XOR lässt sich anhand einer Wahrheitstabelle erklären.

„Exklusives ODER“

• XOR bedeutet „exklusives ODER“ und liefert wahr zurück, wenn genau eine der beiden Eingaben wahr ist.

Der Operator „ungleich“

• XOR gibt 1 zurück, wenn sich die beiden Eingaben unterscheiden, und funktioniert daher genauso wie a ≠ b.

Bedingte Invertierung

• XOR kann als Operator für bedingte Invertierung betrachtet werden, bei dem eine Eingabe bestimmt, ob die andere Eingabe invertiert wird.

Parität oder der Rest bei Division durch 2

• XOR gibt 1 zurück, wenn eine ungerade Anzahl der Eingabebits wahr ist.

Differenz modulo 2

• XOR verhält sich genauso wie der Rest von Addition und Subtraktion bei Division durch 2.

Eigenschaften von XOR

• XOR ist kommutativ und assoziativ, 0 wirkt als neutrales Element, und jede Eingabe ist ihr eigenes Inverses.

Bitweises XOR auf Integern

• Integer lassen sich binär darstellen, sodass XOR bitweise auf sie angewendet werden kann.
• Bitweises XOR hat dieselben Eigenschaften wie boolesches XOR.

Anwendungen von XOR

Verschlüsselung: Kombination von Klartext und Keystream

• XOR wird in der Verschlüsselung verwendet, um Klartext und Keystream zu kombinieren.
• XOR ist in Hardware einfacher als Addition und daher effizient.

Pixelgrafik: Zeichnen, das sich leicht wieder löschen lässt

• In der Computergrafik der 1980er Jahre wurde XOR verwendet, um Zeichnungen zu erstellen, die sich leicht wieder entfernen ließen.
• Mit XOR kann man Pixel erneut zeichnen und so den ursprünglichen Zustand wiederherstellen.

„Half-Adder-Identität“

• XOR repräsentiert das niederwertige Bit einer Addition, AND das höherwertige Bit.
• Für Integer lässt sich Addition mit XOR und AND durchführen.

Dieses Dokument erklärt verschiedene Eigenschaften und Anwendungen von XOR und hilft dabei zu verstehen, wie XOR funktioniert und wofür es nützlich eingesetzt werden kann.