XOR

 (chiark.greenend.org.uk)
1 Punkte von GN⁺ 2025-02-19 | 1 Kommentare | Auf WhatsApp teilen
  • XOR ist eine Operation, die 1 ergibt, wenn sich zwei Bits unterscheiden, und kann als exklusives OR, Ungleichheit, bedingte Invertierung sowie Addition/Subtraktion modulo 2 als ein zusammenhängendes Verhalten verstanden werden
  • Bitweises XOR auf Ganzzahlen verarbeitet jede Stelle unabhängig und macht Unterschiede auf Bitebene sichtbar; es verhält sich wie binäre Addition ohne Übertrag und behält Kommutativität, Assoziativität, das neutrale Element 0 und die Eigenschaft des Selbstinversen bei
  • In der Kryptografie wird es verwendet, um Klartext mit einem Keystream zu kombinieren; in der früheren Pixelgrafik konnte man dasselbe Bild erneut zeichnen, um es zu löschen und so Speicher- und CPU-Last zu verringern
  • Die Eigenschaften von XOR werden direkt in Berechnungen genutzt, die Unterschiede erzeugen und wieder aufheben, etwa bei der Halbaddierer-Identität, beim Bittausch, beim XOR-Swap mit drei Operationen und bei der Gewinnbedingung im Nim-Spiel
  • Es setzt sich fort zur symmetrischen Differenz von Mengen, zu Gruppen vom Exponenten 2, zur nim-sum sowie zu linearer Algebra und Polynomen über GF(2) und ist damit auch mit Fehlererkennungs-, Fehlerkorrektur- und Kryptoverfahren wie Hamming-Code, CRC, AES, GCM und Classic McEliece verbunden

Die Grundbedeutung von XOR

  • XOR ist eine boolesche Operation mit zwei Eingabebits und einem Ausgabebit; die Wahrheitstabelle lautet 00→0, 01→1, 10→1, 11→0
  • Als „exclusive OR“ betrachtet ist das Ergebnis 1, wenn genau eine der beiden Eingaben wahr ist; sind beide wahr, ist das Ergebnis 0
  • Als „not equals“ betrachtet ist a XOR b gleich a ≠ b und liefert 1, wenn sich zwei boolesche Werte unterscheiden
  • Als bedingte Invertierung betrachtet bleibt b bei a=0 unverändert und wird bei a=1 umgedreht
    • Aus demselben Grund kann man auch b als Steuereingang sehen, der a invertiert
  • Aus Sicht der Parität zeigt XOR an, ob die Anzahl der Einsen in den Eingaben ungerade ist
    • Bei zwei Bits ist es gleich a+b mod 2
    • Es ist auch gleich a-b mod 2
    • XORt man mehrere Werte, erkennt man, ob die Gesamtzahl der Einsen in allen Eingaben ungerade oder gerade ist

Algebraische Eigenschaften von XOR

  • XOR erfüllt Kommutativgesetz und Assoziativgesetz
    • a XOR b = b XOR a
    • (a XOR b) XOR c = a XOR (b XOR c)
    • In langen XOR-Listen beeinflussen weder Reihenfolge noch Klammerung das Ergebnis
  • 0 ist das neutrale Element von XOR
    • a XOR 0 = 0 XOR a = a
    • In langen XOR-Listen kann man 0 entfernen
  • Jeder Wert ist sein eigenes Inverses
    • a XOR a = 0
    • Tritt dieselbe Variable zweimal auf, können die beiden Terme gemeinsam gestrichen werden
    • Man kann auch aus bereits gemischten Werten einen bekannten Term entfernen, indem man ihn noch einmal XORt, etwa bei (a XOR b) XOR b = a

Bitweises XOR auf Ganzzahlen

  • Beim bitweisen XOR von Ganzzahlen werden zwei Ganzzahlen binär betrachtet und die Bits jeder Stelle unabhängig XORt
  • Die Eigenschaften von XOR für einzelne Bits gelten unverändert auch für Ganzzahlen
    • a XOR b = b XOR a
    • (a XOR b) XOR c = a XOR (b XOR c)
    • a XOR 0 = a
    • a XOR a = 0
  • Bitweises XOR zeigt Unterschiede auf Bitebene zwischen zwei Ganzzahlen
    • Wenn a=b, dann ist a XOR b = 0
    • Wenn a≠b, dann unterscheidet sich mindestens ein Bit und daher ist a XOR b ≠ 0
    • Die 1-Bits im Ergebnis markieren die Positionen, an denen sich die beiden Eingaben unterscheiden
  • Bitweises XOR kann auch als bedingter Bit-Invertierer gesehen werden
    • Datenbits werden nur an den Positionen invertiert, an denen der Steuerwert 1-Bits hat
    • In ASCII und einigen Nachfolgecodierungen unterscheiden sich lateinische Groß- und Kleinbuchstaben nur in einem Bit; XORt man den Zeichenwert mit 32, kann man zwischen Groß- und Kleinschreibung umschalten
    • Diese Regel gilt nicht für alle Unicode-Zeichen; viele Zeichen haben kein Groß-/Kleinschreibungskonzept oder folgen dieser Regel nicht
  • Bitweises XOR ist dasselbe wie binäre Addition ohne Übertrag
    • An jeder Stelle wird nur modulo 2 addiert, ohne einen Übertrag an die nächste Stelle weiterzugeben

XOR in der Kryptografie

  • In der Kryptografie wird ein Keystream mit derselben Länge wie der Klartext erzeugt, und daraus wird ein Chiffretext gebildet, indem Klartext-Bytes oder -Wörter mit dem Keystream kombiniert werden
  • Für diesen Kombinationsschritt wird üblicherweise XOR verwendet
    • Der Empfänger kann denselben Keystream erneut XORen, um den ursprünglichen Klartext wiederherzustellen
    • Es ist zudem etwas praktischer, dass Sender und Empfänger dieselbe Operation verwenden
  • Die Erzeugung des Keystreams selbst kann deutlich komplexer sein
    • Ein One-Time Pad verwendet echte Zufallsdaten in der vollen Größe der Nachricht und ist unbrechbar, für die meisten Zwecke aber äußerst unpraktisch
    • Üblicherweise erzeugen Stromchiffren oder im Counter Mode betriebene Blockchiffren aus einem kleinen Schlüssel einen Keystream der benötigten Länge
  • Dieses Verfahren kann bei gutem Keystream Vertraulichkeit bieten, aber keine Integrität, also keinen Schutz gegen Manipulation der Nachricht
    • Integritätsschutz ist ein separates Problem
    • Das Weglassen der Integrität ist ein häufiger Fehler bei der Entwicklung kryptografischer Systeme für Einsteiger und führt auch bei komplexeren Verschlüsselungsverfahren zu falschen Ergebnissen
  • In Hardware ist XOR einfacher als Addition
    • Addition benötigt eine Übertragsfortpflanzung zwischen Bits und kostet deshalb mehr Chipfläche und Zeit
    • XOR hat keinen Übertrag und ist in spezialisierter Hardware günstiger

XOR-Zeichnen und Pixelgrafik

  • Heimcomputer der 1980er Jahre hatten nur wenige Bits pro Bildschirmpixel und wenig RAM, sodass es schwierig war, den gesamten Bildschirm doppelt zu speichern
  • Zeichnet man bewegliche Objekte mit XOR, kann man durch erneutes Zeichnen desselben Objekts den ursprünglichen Bildschirm wiederherstellen
    • Man XORt den Pixelwert S des Bildschirms mit dem Pixel M des bewegten Objekts und erhält C; später XORt man dasselbe M erneut und gewinnt S zurück
  • Bei Bildschirmen, auf denen mehrere Pixel in einem Byte gepackt sind oder eine Bitplane-Struktur verwendet wird, ist additive Komposition unhandlich
    • Bei gewöhnlicher Addition kann ein Übertrag von einem Pixel auf das nächste übergehen
    • Bei XOR gibt es überhaupt keinen Übertrag, daher tritt dieses Problem nicht auf
  • Zeichnet man Linien mit XOR, können Pixel an Schnittpunkten zweier Linien zweimal invertiert werden und dadurch zur Hintergrundfarbe zurückkehren, was wie ein kleiner Makel aussieht
    • Dieser Makel wurde als Preis dafür akzeptiert, dass man eine Linie löschen konnte, ohne andere Linien zu beschädigen
  • XOR-Zeichnen war auch für einfache Animationen vorteilhaft
    • Man zeichnet eine neue Linie und zeichnet eine alte Linie erneut, um sie zu löschen; so entsteht das nächste Frame
    • Es ist nicht nötig, alle Pixel oder alle Linien des aktuellen Bildschirms neu zu zeichnen, was Speicher- und CPU-Nutzung reduziert
    • So wurden etwa die bewegten Linien im Spiel Qix von 1981 und auch Fensterumrisse beim Verschieben in frühen GUIs umgesetzt

Halbaddierer-Identität

  • Bei der Addition eines Bits ist das niederwertige Bit von a+b gleich a XOR b, das höherwertige Bit gleich a AND b
  • Dieselbe Beziehung gilt auch für bitweise Operationen auf Ganzzahlen
    • a + b = (a XOR b) + 2 × (a AND b)
    • a XOR b ist die Summe ohne Übertrag, und a AND b enthält die Übertragsbits, die an den jeweiligen Stellen entstanden wären
  • Diese Beziehung kann als Halbaddierer-Identität verstanden werden
    • Ein Hardware-Halbaddierer erzeugt mit AND- und XOR-Gattern den Übertrag und das niederwertige Bit einer Zwei-Bit-Addition
    • Es handelt sich nicht darum, eine vollständige Ganzzahladdition nur mit einfachen Operationen auszudrücken; das + auf der rechten Seite erledigt weiterhin die Übertragsfortpflanzung
  • Diese Identität kann verwendet werden, um den Mittelwert zweier Ganzzahlen ohne Overflow zu berechnen
    • Wenn man einfach a+b bildet und danach nach rechts schiebt, kann das höchstwertige Bit einer 33-Bit-Summe verloren gehen
    • Auf CPUs ohne Carry-Flag oder mit fehlenden bzw. unpraktischen Befehlen wie RRX/RCR ist die Form (a XOR b) >> 1 + (a AND b) eine Alternative
    • Beispiele sind MIPS, RISC-V und DEC Alpha ohne Carry-Flag sowie frühes Arm Thumb ohne RRX
  • Auf CPUs ohne XOR-Befehl kann man die Identität umkehren, um XOR zu erzeugen
    • a XOR b = (a + b) − 2 × (a AND b)
    • Data-General-CPUs der 1970er hatten AND, aber kein bitweises XOR

Tausch von Bits und Werten

  • Das Problem, zwei Bits zu vertauschen, reduziert sich darauf, dass bei gleichen Bits nichts zu tun ist und bei unterschiedlichen Bits beide Bits invertiert werden müssen
  • Mit XOR und Shifts kann man feststellen, ob zwei Bits verschieden sind, und falls nötig beide Positionen invertieren
    • diff_all = input XOR (input >> distance) berechnet die Unterschiede zwischen Bitpaaren mit festem Abstand
    • Mit AND werden nur die relevanten Positionen ausgewählt
    • Die ausgewählten Unterschiede werden auf die andere Position kopiert und dann in den Eingabewert XORt, sodass nur bei Bedarf beide Bits invertiert werden
  • Dieselbe Methode kann auch genutzt werden, um mehrere Bitpaare mit demselben Abstand auf einmal zu vertauschen
    • Statt einer Ein-Bit-Maske verwendet man dann eine Maske mit mehreren Bits
    • Ein Beneš-Netzwerk kann durch das Vertauschen vieler Paare mit gleichem Abstand in mehreren Stufen beliebige Permutationen darstellen
  • Auch ein kompletter XOR-Swap mit drei Operationen für zwei Werte ist möglich
    • a = a XOR b
    • b = b XOR a
    • a = a XOR b
    • So werden zwei Werte auch ohne temporäre Variable vertauscht
  • Der XOR-Swap mit drei Operationen hat ein Aliasing-Problem
    • Für zwei verschiedene Variablen funktioniert er
    • Wenn aber zwei Namen auf denselben Speicherort zeigen, etwa wenn dasselbe Array-Element mit sich selbst vertauscht wird, kann der Wert zu 0 werden

Das Nim-Spiel und XOR

  • Nim ist ein Spiel mit mehreren Haufen, bei dem man abwechselnd einen Haufen auswählt und daraus eine beliebige Anzahl von Spielsteinen, mindestens aber einen, entfernt; wer nicht mehr ziehen kann, verliert
  • In der einfachen Variante von Nim sind Verlustpositionen genau die Positionen, bei denen das bitweise XOR aller Haufengrößen 0 ist
  • Wenn in einer Position mit XOR 0 eine Haufengröße a in einen anderen Wert b geändert wird, ändert sich das gesamte XOR um a XOR b; da a≠b, ist es dann nicht mehr 0
  • In einer Position mit XOR ungleich 0 betrachtet man das höchstwertige 1-Bit des gesamten XOR-Werts x; wählt man einen Haufen, bei dem dieses Bit 1 ist, und reduziert ihn auf pile XOR x, wird das gesamte XOR zu 0
  • Im Beispiel haben die Haufen die Größen 12, 10 und 3, also binär 1100, 1010, 0011; ihr XOR ist 0101
    • Nur der größte Haufen 12 wird durch XOR mit 0101 auf 9 reduziert
    • Der Gewinnzug besteht also darin, aus 12 genau 3 Steine zu entfernen und auf 9 zu gehen

Mathematische Strukturen, die wie XOR aussehen

  • In der Mengenlehre ist die symmetrische Differenz X∆Y eine Operation, die genau die Elemente enthält, die in genau einer der beiden Mengen liegen
    • Betrachtet man die Zugehörigkeit eines Elements als booleschen Wert, ist die symmetrische Differenz dasselbe wie XOR
    • Daher teilt sie XOR-Eigenschaften wie Kommutativität und Assoziativität
  • In der Gruppentheorie ist eine Gruppe vom Exponenten 2 eine Gruppe, in der jedes Element sein eigenes Inverses ist
    • Eine solche Gruppenoperation ist assoziativ und erfüllt als Standardübung auch Kommutativität
    • Dass sich zwei gleiche Elemente gegenseitig aufheben, erinnert an XOR
    • Jede Gruppe vom Exponenten 2 kann als bitweises XOR von Funktionen mit {0,1}-Werten verstanden werden
  • In der Sprague-Grundy-Analyse wird vielen impartial games eine Grundy-Zahl zugeordnet
    • Die Grundy-Zahl eines Composite aus mehreren Teilspielen ergibt sich als bitweises XOR der Grundy-Zahlen der einzelnen Teilspiele
    • In der Spieltheorie wird das bitweise XOR nichtnegativer Ganzzahlen auch nim-sum genannt
  • Der Körper GF(2) ist ein endlicher Körper mit nur den Elementen 0 und 1
    • Addition und Subtraktion verhalten sich wie XOR
    • Multiplikation verhält sich wie AND
    • Daher gilt a AND (b XOR c) = (a AND b) XOR (a AND c)

Lineare Algebra über GF(2) und Fehlerkorrektur

  • Vektoren und Matrizen über GF(2) sind Strukturen, deren Komponenten 0 oder 1 sind; die Addition von Vektoren oder Matrizen ist komponentenweises XOR
  • Die Multiplikation einer Matrix M mit einem Vektor v entspricht dem XOR der von den 1-Komponenten in v ausgewählten Spalten von M
  • Fehlerkorrekturcodes erweitern eine m-Bit-Nachricht zu einem längeren n-Bit-Codewort, sodass einige Bitfehler erkannt oder korrigiert werden können
    • Wenn sich gültige Codewörter in vielen Bits unterscheiden, wird eine kleine Zahl von Bitfehlern nicht in ein anderes gültiges Codewort verwandelt
    • Wenn zwei gültige Codewörter sich in mindestens k Bits unterscheiden, können weniger als k Fehler erkannt werden, und weniger als k/2 Fehler können durch Wahl des nächstgelegenen Codeworts korrigiert werden
  • Lineare Codes verwenden über GF(2) eine Generator Matrix und eine Check Matrix
    • Der Sender erweitert mit der Generator Matrix eine m-Bit-Nachricht zu einem n-Bit-Codewort
    • Der Empfänger prüft mit der Check Matrix, ob das empfangene Codewort gültig ist, und erhält bei Fehlern ein Syndrom
    • Dasselbe Fehlermuster erzeugt unabhängig von der Nachricht stets dasselbe Syndrom
  • Der Hamming code ist ein Beispiel für den Fall, dass die Codelänge n gleich 2^d−1 ist
    • Bei n=15 werden die 15 Bitpositionen mit den 4-Bit-Zahlen von 0001 bis 1111 nummeriert, also allen von 0 verschiedenen Zahlen
    • Der Empfänger XORt die Indizes aller Bits, die 1 sind; ist das Ergebnis 0, liegt ein gültiges Codewort vor
    • Wenn ein einzelnes Bit invertiert wurde, ist das XOR-Ergebnis direkt der Index des invertierten Bits, sodass sich ein 1-Bit-Fehler ohne Lookup-Tabelle korrigieren lässt
    • Ein 15-Bit-Hamming-Code trägt 11 Datenbits und verwendet 4 Bits für die Fehlerkorrektur

Polynome über GF(2), CRC und größere endliche Körper

  • Polynome über GF(2) sind formale Polynome mit Koeffizienten 0 oder 1; Addition entspricht dem XORen der Koeffizienten gleicher Ordnung
  • Die Multiplikation von Polynomen funktioniert wie bei gewöhnlichen Polynomen, indem Teilprodukte gebildet und die Koeffizienten modulo 2 reduziert werden
    • Betrachtet man diese Darstellung als Bitfolge, ähnelt sie der Ganzzahlmultiplikation, nur dass zum Zusammenführen der Teilprodukte statt gewöhnlicher Addition ein carryloses XOR verwendet wird
    • x86 bietet Befehle für carrylose Multiplikation einschließlich CLMUL, und Arm bietet eine Familie von Befehlen für Polynom-Multiplikation
  • CRC verwendet den Rest einer Polynomdivision über GF(2) als Prüfsumme
    • Die gesendete Bitfolge der Nachricht wird als großes Polynom M betrachtet, und man speichert den Rest M mod P bei Division durch ein vereinbartes Polynom P
    • Dies wird zur Prüfung von Ethernet- und ähnlichen Netzwerkpaketen verwendet
    • CRC korrigiert keine Fehler, sondern erkennt sie nur; das passt zu Situationen, in denen fast alle Übertragungen korrekt sind und nur gelegentlich Bitfehler oder Rauschen auftreten
  • Größere endliche Körper lassen sich als Restklassenstrukturen von Polynomen über GF(p) modulo eines irreduziblen Polynoms Q bilden
    • Hat Q den Grad d, dann besitzt der neue endliche Körper p^d Elemente
    • Für p=2 kann man irreduzible Polynome als Bitmuster wie Ganzzahlen schreiben; diese Folge ist in OEIS A014580 verzeichnet
  • Endliche Körper mit Größe als Zweierpotenz tauchen in vielen kryptografischen Techniken auf
    • Der endliche Körper der Größe 2^8 ist ein Kernelement von AES und Twofish
    • Der endliche Körper der Größe 2^128 wird in GCM verwendet, das Bulk Encryption mit Integritätsschutz kombiniert
    • Endliche Körper mit Größe als Zweierpotenz kommen auch in Teilen der elliptic-curve cryptography und in Dekodierungsalgorithmen des Post-Quantum-Verfahrens Classic McEliece vor

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-02-19
Hacker-News-Kommentare

  • Meine liebste verfluchte XOR-Technik ist die XOR-doppelt verkettete Liste: https://en.m.wikipedia.org/wiki/XOR_linked_list
    Jeder Knoten speichert nicht getrennt einen Next-/Previous-Pointer, sondern einen einzelnen Wert, der aus dem XOR beider entsteht. Das ist natürlich kein gültiger Pointer, aber beim Traversieren erhält man durch XOR des Previous-Knoten-Pointers mit dem kombinierten Pointer den Next-Knoten-Pointer, und Traversierung in beide Richtungen ist ebenfalls möglich. Fühlt sich irgendwie illegal an

    • Im Vergleich zu einer normalen doppelt verketteten Liste verliert man die Fähigkeit, das Element zu entfernen, wenn man nur die Adresse des Eintrags hat oder nur Iteratoren, die bei Einfügen/Löschen stabil bleiben. Genau das ist aber oft ein Hauptgrund, überhaupt doppelt verkettete Listen zu verwenden
      Ein weniger grundlegender Nachteil ist, dass es in strikt standardkonformem C extrem lästig ist, eine XOR-verkettete Liste zu implementieren. Der Standard garantiert nicht, dass beim Casten desselben Pointers zu Integern immer derselbe Integer herauskommt, daher muss man praktisch alles zu uintptr_t machen, um eine kanonisierte Integer-Cast-Version beizubehalten
    • Selbst auf 64-Bit-Prozessoren könnte man, wenn man davon ausgeht, dass die meisten Apps mit weniger als 4 GB RAM auskommen, den Speicherbedarf mit einem 32-Bit-Adressraum weiter senken
      Vielleicht sind sogar 16-Bit-Nah-/Relativpointer möglich. Das könnte gut zu Data-Oriented Design passen, etwa mit Blöcken von 64K Elementen, bei denen interne Elemente per uint16-Index referenziert werden
    • Garbage Collector würden das hassen. Oder zumindest diese Datenstruktur für Müll halten
    • Ich frage mich, warum man diese Technik überhaupt verwenden wollen würde
    • Das ist nicht viel anders, als statt eines Pointers die Differenz zweier Pointer zu speichern. Wenn man die Differenz speichert, ist Traversierung in beide Richtungen natürlich ebenfalls möglich

  • Ich habe noch etwas ausgelassen. XOR ist auch eine 3-wise unabhängige lineare Hashfunktion und kann daher für probabilistische approximativ gleichmäßige Stichprobenziehung von Lösungen boolescher Funktionen sowie zum Zählen verwendet werden. Das ist wirklich nützlich und wird verwendet, um Zähler zu bauen, die probabilistisch sind, aber bewiesene Anzahlen liefern. Eine leichter verständliche Erklärung steht hier: https://www.msoos.org/2018/12/how-approximate-model-counting...
    Im Grunde halbiert es den Lösungsraum jedes Mal nahezu exakt. Man fügt also fortlaufend XOR-Bedingungen hinzu, und wenn zum Beispiel noch 10 Lösungen übrig sind und die Anzahl der hinzugefügten XORs k ist, multipliziert man 10 mit 2^k. Weil jedes Mal halbiert wird, erreicht man Größenordnungen von 10 Lösungen schnell, was gut skaliert
    Relevante Papers gibt es unter https://arxiv.org/abs/1306.5726 und https://www.cs.toronto.edu/~meel/Papers/cav20-sgm.pdf, die Tools unter https://github.com/meelgroup/approxmc und https://github.com/meelgroup/unigen. Beim letzten Model-Counting-Wettbewerb haben sie in Kombination mit einem exakten Zähler die anderen Teilnehmer klar dominiert; die Folien dazu sind hier: https://mccompetition.org/assets/files/2024/MC2024_awards.pd...

  • Eine meiner liebsten XOR-Anekdoten stammt von Bryan Cantrill von Oxide, Joyent und Sun, erzählt in dieser Präsentation https://speakerdeck.com/bcantrill/oral-tradition-in-software... und diesem Video https://www.youtube.com/watch?v=4PaWFYm0kEw
    Kurz zusammengefasst, damit man die Links nicht anklicken muss: Als er bei Sun war, sprach er mit seinem Kollegen Roger Faulkner darüber, warum C kein logisches XOR hat. Faulkner meinte, das liege daran, dass man dabei keine Kurzschlussauswertung machen könne, und Brian fand das seltsam. Also fragte Roger Dennis Ritchie per E-Mail, und Ritchie bestätigte, dass Faulkner recht hatte. Cantrills Erzählweise ist schon lustig, aber noch erstaunlicher ist, dass man den Beteiligten einfach direkt fragen konnte

    • DMR war erstaunlich freundlich, hilfsbereit und zugänglich. Mitte der 80er, als ich Undergraduate war, las ich über den „ersten“ Fall, Unix v6 nicht auf eine PDP-11, sondern auf eine Interdata 8/32 portiert zu haben, und schrieb einfach blind eine E-Mail an dmr@research.att.com, um nach mehr Architekturinformationen zu fragen
      Damals gab es weder Google noch Material in der Universitätsbibliothek, und ein paar Tage später fragte er nach meiner Postadresse. Einige Wochen danach kam eine Kopie eines Befehlssatz-Kurzreferenzhandbuchs in meinem Briefkasten an. Es wirkte wie aus der IBM-360-Familie, und ich habe es noch immer
    • C hat ein logisches XOR, nämlich den Operator !=. Anders als andere logische Operatoren müssen seine Argumente auf einen einzelnen Wahrheitswert normalisiert werden, und er passt gut zum Bool-Konvertierungsidiom !! in C
    • Ich verstehe nicht, warum „weil man keine Kurzschlussauswertung machen kann“ ein Hindernis dafür sein soll, den Operator hinzuzufügen. Ich würde mich freuen, wenn das jemand erklären könnte
    • Das Thema beginnt ab 37:18
    • C hatte seit über 40 Jahren den bitweisen XOR-Operator ^: https://www.geeksforgeeks.org/bitwise-operators-in-c-cpp/

  • Ich habe heute gelernt, dass das XORen des Auto-Emojis mit 0x20, also gewissermaßen dessen „Kleinschreibung“, zum Fußgänger-verboten-Emoji wird. Das passt ein bisschen zu perfekt für einen Zufall, deshalb frage ich mich, ob das absichtlich so gemacht wurde und ob das jemand weiß
    Wenn man das zu weit treibt, könnte man auf den seltsamen Gedanken kommen, dass die Kleinschreibung des Auto-Emojis ein Schild für „Fußgänger verboten“ ist

    • Um dem Emoji-entfernenden Kommentar-Renderer von HN zu entgehen, kann man das so prüfen:
      >>> from unicodedata import lookup, name
      >>> name(chr(ord(lookup('AUTOMOBILE')) ^ 0x20))
      'NO PEDESTRIANS'
    • Die Kleinschreibung von Automobile wäre wohl eher Go-Kart
    • :tada: → :tophat:, :rocket: → :mountain_cableway: geht auch

  • Eine gute Alltagsmetapher, um XOR zu erklären, ist ein Lichtschalter an einer Treppe. Unten gibt es einen Schalter, oben einen zweiten, und beide steuern dasselbe Licht
    Anfangs stehen beide auf Aus; wenn man den unteren Schalter einschaltet, geht das Licht an. Geht man die Treppe hoch und schaltet den oberen Schalter ein, stehen beide Schalter auf „Ein“, aber das Licht ist aus. Das Licht ist nur dann an, wenn genau ein Schalter auf „Ein“ und der andere auf „Aus“ steht; sonst ist es aus

    • Vielleicht hat der Elektriker in unserem Büro die Verkabelung vermurkst. In einem Raum gibt es zwei Schalter, und wenn ich darüber nachdenke, verhalten sie sich eher wie ein AND-Gatter als wie XOR. Die beiden Schalter im Wohnzimmer funktionieren aber definitiv wie XOR

  • Ich mag es überhaupt nicht, dass für diese logische Funktion so oft der Name XOR, also „exklusives ODER“, verwendet wird. Fast immer ist eigentlich „Summe modulo 2“, also Parität, gemeint und nicht exklusives ODER
    „Summe modulo 2“/Parität und „exklusives ODER“ sind unterschiedliche logische Funktionen und stimmen nur zufällig überein, wenn es genau 2 Eingabeoperanden gibt. Das liegt daran, dass es unter 2 nur eine ungerade Zahl gibt
    Bei 3 oder mehr Eingängen ist das, was die meisten XOR nennen, in Wirklichkeit Parität: also 1 genau dann, wenn eine ungerade Anzahl von Eingängen 1 ist. Exklusives ODER ist dagegen bei 3 oder mehr Eingängen die Funktion, die nur dann 1 ergibt, wenn genau ein Eingang 1 und alle übrigen 0 sind
    In Computerhardware ist Parität viel wichtiger als exklusives ODER. Der Hauptgrund ist, dass Addition modulo 2 als Baustein zur Implementierung der Addition größerer Zahlen dient. In der Mathematik hingegen ist exklusives ODER viel wichtiger als Parität
    Zum Beispiel basieren Quantoren, die ausdrücken, dass ein Prädikat für einige Elemente einer Menge, für alle Elemente oder für genau ein Element wahr ist, jeweils auf ODER, UND und exklusivem ODER. Das „or“ in natürlicher Sprache bedeutet immer inklusives ODER oder exklusives ODER, aber nie die Parität, die viele Programmierer XOR nennen
    In der Programmierung muss man die logische Funktion exklusives ODER selten tatsächlich berechnen, aber zur Beschreibung des Programmverhaltens wird sie oft verwendet. Etwa wenn man sagt, dass in einer select/case/switch-Verbundanweisung der erste oder der zweite oder der dritte Zweig ausgeführt wird, oder wenn man die möglichen Typen des aktuellen Werts einer Union-/Sum-Typ-Variablen beschreibt

    • Der elektrotechnische Symbolstandard IEC 60617 behandelt das korrekt. Ein XOR-Gatter wird mit =1, ein Paritätsgatter mit 2k + 1 gekennzeichnet. Wer aber Schaltungsentwurfssoftware für PCBs oder FPGAs verwendet, kann trotzdem noch etwas anderes bekommen als erwartet
    • In der Mathematik nennt man das den Eindeutigkeitsquantor; dafür gibt es auch ein eigenes Symbol: ∃!
    • Die Erklärung, dass „exklusives ODER“ bei 3 oder mehr Eingängen genau dann wahr ist, wenn genau einer 1 ist, braucht eine Begründung
    • Diese Auslegung wird auch im Hauptessay behandelt

  • Es gibt auch die verteilte Kademlia-Hash-Tabelle: kademlia distributed hash table. Die große Idee ist, dass jeder Knoten zufällige Bits aus dem Bereich [0, 2^m) erhält und die Distanz per XOR definiert wird. Gesucht ist ein verteilter Algorithmus, mit dem man Informationen schnell von X nach Y schicken kann, ohne das gesamte Netzwerk zu kennen
    Man kann allein mit Mathematik beweisen, dass das funktioniert, aber meine liebste visuelle Intuition ist diese: Angenommen, der Startknoten X möchte den Knoten k finden. Definiere den „X-Distanzbaum“ als Binärbaum, dessen Blattindizes 0, 1, 2 ... sind, und versieh jedes Blatt mit dem Label X^leaf_index, sodass es die Distanz zu X darstellt. Weil zum Beispiel dist(x, x) = x^x = 0 gilt, landet das Label des ursprünglichen Knotens X auf dem ganz linken Blatt 0
    Das Intervall [2^i, 2^(i+1)) ist ein bestimmter Teilbaum des X-Distanzbaums. Wenn man weiß, dass die Distanz zu k in dieses Intervall fällt, fragt man irgendeinen Knoten Y darin als ungefähren Nachbarn an
    Ganz gleich, welches Y man wählt: Im Y-Distanzbaum ist das resultierende Präfix immer eine Permutation des gewählten Teilbaums [2^i, 2^(i+1)) aus dem X-Distanzbaum. Genauer kann man es als labels_of_leaves_of_X([2^i, 2^(i+1))) == labels_of_leaves_of_Y([0, 2^i)) auffassen. Die Indizes beziehen sich auf die Distanz, aber die Labels können unterschiedlich sein
    Für Vergleiche mit anderen verteilten Hash-Tabellen wie Chord gibt es mathematisch und empirisch deutlich rigoroseres Material. Aber diese visuelle Intuition vermittelt ein Gefühl dafür, was die „Symmetrie“ von Kademlia ist: Jeder hat seine eigenen lokalen Nachbarn und seinen eigenen Teilbaum
    Chord dagegen scheint, selbst wenn es bidirektional implementiert wird, doppelt so viel Speicher zu brauchen und riskanter in der Implementierung zu sein, und es ist schwer, ein solches Maß an „Isolierung“ zu erreichen. Das gleitende Nachbarfenster der Größe S ist ständig in Bewegung, und pro Bit gibt es 2^m unterschiedliche Nachbarn. Auch wenn viele Nachbarn ähnlich aussehen, ist das nicht besonders elegant
    Kademlia hat 1 + 2 + 4 ... + 2^m-1 Nachbarn, und das Ganze ist ordentlich strukturiert

  • Falls sich das jemand fragt: Das ist Simon Tatham aus Simon Tatham's Portable Puzzle Collection. Wenn ihr das nicht kennt, ist das eine gute Beschäftigung für langweilige Offline-Momente
    Ich habe in der Oberstufe viel zu viel Zeit damit verbrannt: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

  • Heutzutage werden viele spezialisierte Optimierungs-Solver, zum Beispiel Ising Machines, mit dem XOR-Problem benchmarked. Tatsächlich ist das Lösen mehrerer XOR-Klauseln per Gauß-Elimination in polynomialer Zeit möglich, daher ist der praktische Nutzen etwas begrenzt, aber da die Solver alle exponentielle Skalierung zeigen, ist es dennoch eine gute Methode, ihre Leistung einzuschätzen.
    Eine zweite interessante Implementierung hängt mit dem McEliece-Kryptosystem zusammen. Es handelt sich um ein Public-Key-Kryptosystem aus den 70er-Jahren, das heute wegen seiner Quantenresistenz wieder Aufmerksamkeit erhält. Ein Entschlüsselungsangriff ist das Problem, eine Lösung für ein System von XOR-Gleichungen zu finden; auch das ist in polynomialer Zeit lösbar, allerdings unter der zusätzlichen Bedingung, dass die Hamming-Distanz einem bestimmten Wert entspricht, der im öffentlichen Schlüssel enthalten ist.

  • Als ich für die Programmierung des TI-83 Z80-Assembly lernte, zählte jedes einzelne Byte Maschinencode. Der gesamte Speicher des Taschenrechners betrug nämlich nur 24 KB.
    Um das Hauptakkumulator-Register a auf 0 zu initialisieren, verwendete man XOR a statt LD a, 0. Bei Rechenbefehlen ist a der implizite Operand, daher XORt XOR a a mit sich selbst, und der gesamte Befehl ist nur 1 Byte lang. Wenn man dagegen 0 explizit in a laden will, muss das Literal 0 im Opcode enthalten sein, daher ist LD a, 0 ein 2-Byte-Befehl.