Wie funktioniert XOR variable swapping arbeiten?

Question

Kann mir jemand erklären, wie XOR vertauschen von zwei Variablen ohne temp-variable funktioniert?

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

Ich verstehen, WAS es tut, aber kann jemand zu Fuß mich durch die Logik, 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

Durch Einsetzen,

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

Da xor ist voll assoziativ und kommutativ:

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

Da 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 jedes x,

y2 = x0
x2 = y0

Und der Swap erfolgt.

Answer 2

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

Zurück in dem Tag, wenn wir einfach einzigen Zyklus oder mehrere Zyklen CPUs hatten, es billiger war, diesen Trick zu verwenden teure Speicher Dereferenzierungen oder Verschütten Register auf den Stapel zu vermeiden. Allerdings haben wir jetzt CPUs mit massiven Pipelines statt. Die Pipeline des P4 reichte von 20 bis 31 (oder so) Stufen in ihren Rohrleitungen, wo jede Abhängigkeit zwischen Lese und Schreiben in ein Register könnte das Ganze verursacht zu. Der xor Swap hat einige sehr schwere Abhängigkeiten zwischen A und B, die eigentlich nicht Sache überhaupt, aber die Pipeline in der Praxis abgewürgt. Eine ins Stocken geriet Pipeline führt zu einem langsamen Codepfad, und wenn dieser Swap in Ihrer inneren Schleife ist, Sie gehen sehr langsam zu bewegen.

In der allgemeinen Praxis kann der Compiler herauszufinden, was Sie wirklich wollen, wenn Sie einen Swap mit einer temporären Variable tun und es zu einer einzigen XCHG Anweisung zusammenstellen können. die xor Swap macht es viel schwieriger für den Compiler Ihre Absicht zu erraten, und daher viel weniger wahrscheinlich, um es richtig zu optimieren. Nicht Code Wartung zu erwähnen, etc.

Answer 3

Ich mag daran denken grafisch nicht numerisch.

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

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

Nun zu mir, ist XOR eine Invert-Operation und es zweimal tun, ist 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!

Answer 4

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 versteht ein wenig leichter durch Verständnis Trick, dass ^ kann wie folgt beschrieben werden + oder - . So wie:

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

, so:

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

Answer 5

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

 // 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 eine 2-Wege-verkettete Liste in einem einzigen „Zeiger“. Angenommen, Sie haben eine Liste von Speicherblöcken an den Adressen A, B und C. Das erste Wort in jedem Block ist jeweils:

 // 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 haben A zu blockieren, es gibt Ihnen die Adresse von B zu C erhalten, nehmen Sie den „Zeiger“ in B und A subtrahieren, und so weiter. Es funktioniert genauso gut nach hinten. Um auf der Liste auszuführen, müssen Sie Zeiger auf zwei aufeinanderfolgende Blöcke zu halten. Natürlich würden Sie XOR anstelle der Addition / Subtraktion verwenden, so würden Sie nicht über einen Überlauf sorgen.

Sie dies zu einem „verknüpften Web“ erweitern könnten, wenn Sie etwas Spaß haben wollen.

Answer 6

Die meisten Menschen würden swap zwei Variablen x und y über eine temporäre variable, wie diese:

tmp = x
x = y
y = tmp

Hier ist eine saubere Programmierung trick, um swap zwei Werte, ohne dass eine temp:

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

Mehr details Tauschen Sie zwei Variablen mit XOR

Auf der Linie 1 verbinden wir x und y (mit XOR), um diese "hybrid" und wir speichern es zurück in x.XOR ist eine großartige Möglichkeit, Informationen zu speichern, denn Sie können es entfernen, indem Sie eine XOR wieder.

Auf der Linie 2.Wir XOR-hybrid mit y, die bricht all die y-Daten, so dass uns nur mit x.Wir speichern in diesem Ergebnis wieder in y, so jetzt Sie haben getauscht.

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

---

Der computer hat tatsächlich eine implizite "temp" - variable, die speichert Zwischenergebnisse, bevor Sie zu schreiben zurück, um ein register.Zum Beispiel, wenn Sie hinzufügen 3 zu einem register (in Maschinen-Sprache pseudocode):

ADD 3 A // add 3 to register A

Die ALU (Arithmetic Logic Unit) ist eigentlich das, was führt die Anweisung 3+A.Es nimmt die Eingänge (3,A) und erzeugt eine Folge (3 + A), die die CPU speichert dann wieder in die ursprüngliche registrieren.So, wir verwendet die ALU als temporären Speicherbereich bevor wir die endgültige Antwort.

Nehmen wir die ALU implizite temporäre Daten für selbstverständlich, aber es ist immer da.In ähnlicher Weise wird das ALU zurückgeben können das zwischen-Ergebnis der XOR-im Falle von x = x xor y, an welchem Punkt die CPU speichert Sie in x-original-register.

Weil wir nicht gewohnt ist zu denken, über die Armen, vernachlässigten ALU, der XOR-swap magisch scheint, weil es nicht explizit temporäre variable.Einige Maschinen haben eine 1-Schritt-exchange-XCHG Anweisung swap zwei Register.

Answer 7

@VonC hat es richtig, es ist ein netter mathematischer Trick . Stellen Sie sich vor 4-Bit-Worte und sehen, 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 8

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

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

Um zu verstehen, Warum das funktioniert zunächst zur Kenntnis, dass:

1. XOR wird ein 1 nur erzeugen, wenn genau eine seiner Operanden 1 ist, und das andere ist Null;
2. XOR ist commutative , um eine XOR b = b XOR a;
3. XOR ist assoziativer so (a XOR b) XOR c = a XOR (b XOR c); und
4. a XOR a = 0 (dies aus der Definition offensichtlich sein sollte in 1 oben)

nach dem Schritt (1) wird die Binärdarstellung einer muß 1-Bits nur in den Bitpositionen, wobei a und b entgegengesetzte Bits haben. Das heißt, 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
    = A XOR (b XOR b) weil XOR ist assoziativ
   = A XOR 0 wegen [4] oben
   = A 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 ein, weil XOR kommutativ
    = B XOR (a XOR a) weil XOR assoziative
ist     = B XOR 0 wegen [4] oben
    = B aufgrund Definition von XOR (siehe 1 oben)

Weitere Informationen hier: notwendig und ausreichend

Answer 9

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

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

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

Die genaue 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, das ist ganz einfach, da

sehen

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

und

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

Hoffe, das hilft. Diese Erklärung ist bereits gegeben worden ... aber nicht ganz klar imo.