Wie funktioniert der Austausch von XOR-Variablen?

Kann mir jemand erklären, wie das XOR-Austauschen von zwei Variablen ohne temporäre Variable funktioniert?

void xorSwap (int *x, int *y)
{
    if (x != y) {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}

Ich verstehe, WAS es tut, aber kann mich jemand durch die Logik führen, wie es funktioniert?

Sie können sehen, wie es funktioniert, indem Sie die Ersetzung durchführen:

x1 = x0 xor y0
y2 = x1 xor y0
x2 = x1 xor y2

Ersetzen,

x1 = x0 xor y0
y2 = (x0 xor y0) xor y0
x2 = (x0 xor y0) xor ((x0 xor y0) xor y0)

Weil xor vollständig assoziativ und kommutativ ist:

y2 = x0 xor (y0 xor y0)
x2 = (x0 xor x0) xor (y0 xor y0) xor y0

Da x xor x == 0für jedes x,

y2 = x0 xor 0
x2 = 0 xor 0 xor y0

Und da x xor 0 == xfür jedes x,

y2 = x0
x2 = y0

Und der Tausch ist erledigt.

Andere Leute haben es erklärt, jetzt möchte ich erklären, warum es eine gute Idee war, aber jetzt nicht.

Früher, als wir einfache Einzelzyklus- oder Mehrzyklus-CPUs hatten, war es billiger, diesen Trick zu verwenden, um kostspielige Speicherstörungen oder das Verschütten von Registern auf den Stapel zu vermeiden. Wir haben jetzt jedoch stattdessen CPUs mit massiven Pipelines. Die Pipeline des P4 reichte von 20 bis 31 (oder so) Stufen in ihren Pipelines, wobei jede Abhängigkeit zwischen Lesen und Schreiben in ein Register dazu führen könnte, dass das Ganze ins Stocken gerät. Der xor-Swap weist einige sehr starke Abhängigkeiten zwischen A und B auf, die eigentlich gar nicht wichtig sind, aber die Pipeline in der Praxis blockieren. Eine blockierte Pipeline verursacht einen langsamen Codepfad. Wenn sich dieser Swap in Ihrer inneren Schleife befindet, bewegen Sie sich sehr langsam.

In der Regel kann Ihr Compiler herausfinden, was Sie wirklich tun möchten, wenn Sie einen Swap mit einer temporären Variablen durchführen, und ihn zu einer einzelnen XCHG-Anweisung kompilieren. Die Verwendung des xor-Swaps erschwert es dem Compiler erheblich, Ihre Absicht zu erraten, und ist daher weniger wahrscheinlich, dass er sie richtig optimiert. Ganz zu schweigen von der Code-Wartung usw.

Ich denke lieber grafisch als numerisch darüber nach.

Angenommen, Sie beginnen mit x = 11 und y = 5. In der Binärdatei (und ich werde eine hypothetische 4-Bit-Maschine verwenden) sind hier x und y

       x: |1|0|1|1|   -> 8 + 2 + 1
       y: |0|1|0|1|   -> 4 + 1

Für mich ist XOR eine Invertierungsoperation und zweimal ist dies ein Spiegel:

     x^y: |1|1|1|0|
 (x^y)^y: |1|0|1|1|   <- ooh!  Check it out - x came back
 (x^y)^x: |0|1|0|1|   <- ooh!  y came back too!

Hier ist eine, die etwas einfacher zu verstehen sein sollte:

int x = 10, y = 7;

y = x + y; //x = 10, y = 17
x = y - x; //x = 7, y = 17
y = y - x; //x = 7, y = 10

Jetzt kann man den XOR-Trick etwas leichter verstehen, wenn man versteht, dass ^ als + oder - betrachtet werden kann . Genauso wie:

x + y - ((x + y) - x) == x 

, damit:

x ^ y ^ ((x ^ y) ^ x) == x

Die meisten Leute würden zwei Variablen x und y mit einer temporären Variablen wie folgt tauschen:

tmp = x
x = y
y = tmp

Hier ist ein netter Programmiertrick, um zwei Werte zu tauschen, ohne eine Temperatur zu benötigen:

x = x xor y
y = x xor y
x = x xor y

Weitere Details finden Sie unter Tauschen Sie zwei Variablen mit XOR aus

In Zeile 1 kombinieren wir x und y (mit XOR), um diesen „Hybrid“ zu erhalten, und speichern ihn wieder in x. XOR ist eine großartige Möglichkeit, Informationen zu speichern, da Sie sie entfernen können, indem Sie erneut ein XOR ausführen.

In Zeile 2. XOR wir den Hybrid mit y, wodurch alle y-Informationen gelöscht werden und wir nur mit x zurückbleiben. Wir speichern dieses Ergebnis wieder in y, also haben sie jetzt getauscht.

In der letzten Zeile hat x immer noch den Hybridwert. Wir XOR es noch einmal mit y (jetzt mit dem ursprünglichen Wert von x), um alle Spuren von x aus dem Hybrid zu entfernen. Dies lässt uns mit y und der Tausch ist abgeschlossen!

Der Computer verfügt tatsächlich über eine implizite temporäre Variable, die Zwischenergebnisse speichert, bevor sie in ein Register zurückgeschrieben werden. Wenn Sie beispielsweise einem Register 3 hinzufügen (im maschinensprachlichen Pseudocode):

ADD 3 A // add 3 to register A

Die ALU (Arithmetic Logic Unit) führt tatsächlich den Befehl 3 + A aus. Es nimmt die Eingänge (3, A) und erzeugt ein Ergebnis (3 + A), das die CPU dann wieder in das ursprüngliche Register von A speichert. Also haben wir die ALU als temporären Arbeitsbereich verwendet, bevor wir die endgültige Antwort hatten.

Wir halten die impliziten temporären Daten der ALU für selbstverständlich, aber sie sind immer da. In ähnlicher Weise kann die ALU im Fall von x = x xor y das Zwischenergebnis des XOR zurückgeben, wobei die CPU es an diesem Punkt im ursprünglichen Register von x speichert.

Da wir es nicht gewohnt sind, an die arme, vernachlässigte ALU zu denken, erscheint der XOR-Swap magisch, da er keine explizite temporäre Variable enthält. Einige Maschinen verfügen über einen einstufigen XCHG-Austauschbefehl zum Austauschen von zwei Registern.

Der Grund, warum es funktioniert, ist, dass XOR keine Informationen verliert. Sie könnten dasselbe mit gewöhnlicher Addition und Subtraktion tun, wenn Sie den Überlauf ignorieren könnten. Wenn das Variablenpaar A, B ursprünglich die Werte 1,2 enthält, können Sie sie folgendermaßen austauschen:

 // A,B  = 1,2
A = A+B // 3,2
B = A-B // 3,1
A = A-B // 2,1

Übrigens gibt es einen alten Trick zum Codieren einer in beide Richtungen verknüpften Liste in einem einzelnen "Zeiger". Angenommen, Sie haben eine Liste von Speicherblöcken an den Adressen A, B und C. Das erste Wort in jedem Block lautet:

 // first word of each block is sum of addresses of prior and next block
 0 + &B   // first word of block A
&A + &C   // first word of block B
&B + 0    // first word of block C

Wenn Sie Zugriff auf Block A haben, erhalten Sie die Adresse B. Um zu C zu gelangen, nehmen Sie den "Zeiger" in B und subtrahieren A und so weiter. Es funktioniert genauso gut rückwärts. Um entlang der Liste zu laufen, müssen Sie Zeiger auf zwei aufeinanderfolgende Blöcke behalten. Natürlich würden Sie XOR anstelle von Addition / Subtration verwenden, sodass Sie sich keine Gedanken über einen Überlauf machen müssen.

Sie können dies auf ein "verknüpftes Web" erweitern, wenn Sie Spaß haben möchten.

@VonC hat es richtig, es ist ein ordentlicher mathematischer Trick. Stellen Sie sich 4-Bit-Wörter vor und prüfen Sie, ob dies hilft.

word1 ^= word2;
word2 ^= word1;
word1 ^= word2;


word1    word2
0101     1111
after 1st xor
1010     1111
after 2nd xor
1010     0101
after 3rd xor
1111     0101

Grundsätzlich besteht der XOR-Ansatz aus drei Schritten:

a '= a XOR b (1)
b' = a 'XOR b (2)
a' = a 'XOR b' (3)

Um zu verstehen, warum dies funktioniert, beachten Sie zunächst Folgendes:

1. XOR erzeugt nur dann eine 1, wenn genau einer seiner Operanden 1 und der andere Null ist.
2. XOR ist kommutativ, also a XOR b = b XOR a;
3. XOR ist assoziativ, also (a XOR b) XOR c = a XOR (b XOR c); und
4. a XOR a = 0 (dies sollte aus der Definition in 1 oben ersichtlich sein )

Nach Schritt (1) hat die binäre Darstellung von a nur an den Bitpositionen, an denen a und b entgegengesetzte Bits haben, 1 Bits. Das ist entweder (ak = 1, bk = 0) oder (ak = 0, bk = 1). Wenn wir nun die Substitution in Schritt (2) durchführen, erhalten wir:

b '= (a XOR b) XOR b
= a XOR (b XOR b), weil XOR assoziativ ist
= a XOR 0 wegen [4] oben
= a aufgrund der Definition von XOR (siehe 1 oben)

Jetzt können wir in Schritt (3) ersetzen:

a ”= (a XOR b) XOR a
= (b XOR a) XOR a, weil XOR kommutativ ist
= b XOR (a XOR a), weil XOR assoziativ ist
= b XOR 0, weil [4] oben
= b aufgrund der Definition von XOR (siehe 1 oben)

Nähere Informationen hier: Notwendig und ausreichend

Als Randnotiz habe ich dieses Rad vor einigen Jahren unabhängig voneinander neu erfunden, indem ich ganze Zahlen ausgetauscht habe, indem ich Folgendes getan habe:

a = a + b
b = a - b ( = a + b - b once expanded)
a = a - b ( = a + b - a once expanded).

(Dies ist oben auf schwer lesbare Weise erwähnt),

Die gleiche Argumentation gilt für xor-Swaps: a ^ b ^ b = a und a ^ b ^ a = a. Da xor kommutativ ist, x ^ x = 0 und x ^ 0 = x, ist dies seitdem ziemlich leicht zu erkennen

= a ^ b ^ b
= a ^ 0
= a

und

= a ^ b ^ a 
= a ^ a ^ b 
= 0 ^ b 
= b

Hoffe das hilft. Diese Erklärung wurde bereits gegeben ... aber nicht sehr klar imo.

Ich möchte nur eine mathematische Erklärung hinzufügen, um die Antwort vollständiger zu machen. In der Gruppentheorie ist XOR eine abelsche Gruppe , auch kommutative Gruppe genannt. Dies bedeutet, dass es fünf Anforderungen erfüllt: Abschluss, Assoziativität, Identitätselement, Inverses Element, Kommutativität.

XOR-Swap-Formel:

a = a XOR b
b = a XOR b
a = a XOR b 

Erweitern Sie die Formel, ersetzen Sie a, b durch die vorherige Formel:

a = a XOR b
b = a XOR b = (a XOR b) XOR b
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b

Kommutativität bedeutet "a XOR b" gleich "b XOR a":

a = a XOR b
b = a XOR b = (a XOR b) XOR b
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b

Assoziativität bedeutet "(a XOR b) XOR c" gleich "a XOR (b XOR c)":

a = a XOR b
b = a XOR b = (a XOR b) XOR b 
            = a XOR (b XOR b)
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b 
            = b XOR (a XOR a) XOR (b XOR b)

Das inverse Element in XOR ist selbst, es bedeutet, dass jeder Wert XOR mit sich selbst Null ergibt:

a = a XOR b
b = a XOR b = (a XOR b) XOR b 
            = a XOR (b XOR b) 
            = a XOR 0
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b 
            = b XOR (a XOR a) XOR (b XOR b) 
            = b XOR 0 XOR 0

Das Identitätselement in XOR ist Null. Dies bedeutet, dass jeder Wert XOR mit Null unverändert bleibt:

a = a XOR b
b = a XOR b = (a XOR b) XOR b 
            = a XOR (b XOR b) 
            = a XOR 0 
            = a
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b 
            = b XOR (a XOR a) XOR (b XOR b) 
            = b XOR 0 XOR 0 
            = b XOR 0
            = b

Weitere Informationen erhalten Sie in der Gruppentheorie .