Wie funktioniert das XOR-Variablen-Swapping?

Question

Kann mir jemand erklären, wie XOR-Swapping von zwei Variablen ohne Temp-Variable funktioniert?

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

Ich verstehe, was es tut, aber kann jemand mich durch die Logik gehen, wie es funktioniert?

Answer 1

Sie können sehen, wie es funktioniert, indem die Substitution tun:

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

Substituieren

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

Da xor voll assoziativ ist und kommutativ:

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

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

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

Und da x xor 0 == x für alle x,

y2 = x0 
x2 = y0 

Und der Swap erfolgt.

Answer 2

Die meisten Menschen würden zwei Variablen x und y vertauschen eine temporäre Variable, wie dies mit:

tmp = x 
x = y 
y = tmp 

Hier ist eine saubere Programmierung Trick zwei Werte zu tauschen, ohne eine temporäre zu benötigen:

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

Mehr Details in

In Zeile 1 kombinieren wir x und y (mit XOR), um diese "hybri d "und wir speichern es zurück in x. XOR ist eine großartige Möglichkeit, Informationen zu speichern, da Sie sie durch erneutes XOR entfernen können.

In Zeile 2. Wir XOR der Hybrid mit y, die alle y Informationen löscht, so dass wir nur mit x. Wir speichern dieses Ergebnis wieder in y, also haben sie jetzt getauscht.

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

---

Der Computer hat tatsächlich eine implizite „temp“ Variable, die sie zurück in ein Register zu schreiben, bevor die Zwischenergebnisse speichert. Zum Beispiel, wenn Sie 3 in ein Register (in Maschinensprache Pseudo-Code) hinzufügen:

ADD 3 A // add 3 to register A 

Die ALU (Arithmetic Logic Unit) ist eigentlich das, was die A-Befehl 3 + ausführt. Er nimmt die Eingaben (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 Scratch Space benutzt, bevor wir die endgültige Antwort hatten.

Wir nehmen die impliziten temporären Daten der ALU als selbstverständlich an, aber es ist immer da. Auf ähnliche Weise kann die ALU das Zwischenergebnis des XOR im Fall von x = x x oder y zurückgeben, wobei die CPU es zu diesem Zeitpunkt in das ursprüngliche Register von x speichert.

Da wir es nicht gewohnt sind, über die arme, vernachlässigte ALU nachzudenken, erscheint der XOR-Tausch magisch, weil er keine explizite temporäre Variable hat. Einige Maschinen haben einen 1-stufigen Austausch-XCHG-Befehl, um zwei Register auszutauschen.

Answer 3

Hier ist eine, die etwas einfacher sein sollte grok:

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 

Nun kann man die XOR verstehen ein wenig leichter Trick durch das Verständnis, dass ^ kann man sich als +oder-. So wie:

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

, so:

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

Answer 4

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

Damals, als wir einfache Single-Cycle- oder Multi-Cycle-CPUs hatten, war es billiger, diesen Trick zu verwenden, um kostspielige Speicher-Dereferenzierungen zu vermeiden oder Register auf den Stack zu verschütten. Allerdings haben wir jetzt CPUs mit massiven Pipelines. Die P4-Pipeline reichte von 20 bis 31 (oder so) Stufen in ihren Pipelines, wo jede Abhängigkeit zwischen Lesen und Schreiben in ein Register das Ganze zum Stillstand bringen konnte. Der XOR-Tausch hat einige sehr starke Abhängigkeiten zwischen A und B, die eigentlich gar nichts ausmachen, aber die Pipeline in der Praxis aufhalten. Eine angehaltene Pipeline verursacht einen langsamen Codepfad, und wenn sich dieser Austausch in Ihrer inneren Schleife befindet, werden Sie sich sehr langsam bewegen.

In der Regel kann Ihr Compiler herausfinden, was Sie wirklich tun wollen, wenn Sie einen Tausch mit einer temporären Variable durchführen und ihn zu einem einzigen XCHG-Befehl kompilieren können. Die Verwendung des XOR-Swap macht es für den Compiler viel schwieriger, Ihre Absicht zu erraten, und daher ist es sehr viel weniger wahrscheinlich, dass es richtig optimiert wird. Nicht zu erwähnen, Code-Wartung, etc.

Answer 5

@VonC hat es richtig, es ist eine nette mathematische Trick. Stellen Sie sich 4-Bit-Wörter vor und sehen Sie, ob das 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 

Answer 6

Grundsätzlich gibt es 3 Schritte in dem XOR-Ansatz:

a '= a XOR b (1)
b' = a XOR‘XOR B (2)
a“ a =‘ b‘(3)

Um zu verstehen, warum diese erste Note funktioniert das:

1. XOR erzeugt nur dann eine 1, wenn genau einer der Operanden 1 ist und der andere Null ist;
2. XOR ist kommutative so ein XOR b = b XOR a;
3. XOR ist assoziativ so (ein XOR b) XOR c = ein XOR (b XOR c); und
4. a XOR a = 0 (dies sollte aus der Definition in 1 obigen offensichtlich sein)

nach Schritt (1) wird die Binärdarstellung einer muß 1-Bits nur in den Bitpositionen, wo ein und b haben entgegengesetzte Bits. Das ist entweder (ak = 1, bk = 0) oder (ak = 0, bk = 1). Nun, wenn wir die Substitution in Schritt tun (2) erhalten wir:

b‘= (a XOR b) XOR b
eine XOR (b XOR b) = weil XOR assoziativ ist
eine XOR 0 = wegen [4] über
einen aufgrund Definition von XOR = (siehe 1 oben)

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

a“= (a XOR b) XOR ein
= (b XOR a) XOR a weil XOR ist comm utative
= b XOR (a XOR a) weil XOR assoziativ ist
= b XOR 0 wegen [4] oben
= b aufgrund Definition von XOR (siehe 1 oben)

Ausführlichere Informationen hier : Necessary and Sufficient

Answer 7

Der Grund, warum es funktioniert, ist, weil XOR keine Informationen verliert. Sie könnten dasselbe mit gewöhnlicher Addition und Subtraktion tun, wenn Sie den Überlauf ignorieren könnten. Wenn zum Beispiel die Variable Paar A, ursprünglich B die Werte 1,2 enthält, können Sie sie wie folgt tauschen:

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

BTW es ist ein alter Trick zum Codieren eines 2-Wege-verkettete Liste in einem einzigen „Zeiger ". Sie eine Liste der Speicherblöcke an den Adressen A, B und C. Das erste Wort in jedem Block ist jeweils Angenommen haben:

// 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 Zugang haben zu einem Block, es gibt Ihnen die Adresse von B Um zu C zu gelangen, nehmen Sie den "Zeiger" in B und subtrahieren Sie A, und so weiter. Es funktioniert genauso gut rückwärts. Um die Liste zu durchlaufen, müssen Sie die Zeiger auf zwei aufeinanderfolgende Blöcke halten.Natürlich würden Sie XOR anstelle von Addition/Subtraktion verwenden, damit Sie sich keine Gedanken über Überlauf machen müssen.

Sie könnten dies zu einem "verlinkten Web" erweitern, wenn Sie Spaß haben möchten.

Answer 8

Als Randbemerkung ich, indem Sie in Form von Austausch ganzer Zahlen vor einigen Jahren dieses Rad unabhängig neu erfunden:

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

(Diese oben in schwierigem erwähnt Art und Weise zu lesen),

Die Genau dasselbe 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, das ist ganz leicht zu sehen, da

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

und

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

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

Answer 9

Ich mag es eher grafisch als numerisch zu denken.

Angenommen, Sie mit x = 11 und y = 5 In binären starten (und ich werde eine hypothetische 4-Bit-Maschine verwenden), hier x und y

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

Nun zu mir, XOR ist ein Invert-Betrieb und es zweimal ein Spiegel tun:

 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!