Frage Warum schlägt das Tauschen von Werten mit XOR bei Verwendung dieses zusammengesetzten Formulars fehl?


Ich habe diesen Code gefunden, um zwei Zahlen zu vertauschen, ohne eine dritte Variable zu verwenden, die das XOR benutzt ^ Operator.

Code: 

int i = 25;
int j = 36;
j ^= i;       
i ^= j;
j ^= i;

Console.WriteLine("i:" + i + " j:" + j);

//numbers Swapped correctly
//Output: i:36 j:25

Jetzt habe ich den obigen Code in diesen äquivalenten Code geändert.

Mein Code: 

int i = 25;
int j = 36;

j ^= i ^= j ^= i;   // I have changed to this equivalent (???).

Console.WriteLine("i:" + i + " j:" + j);

//Not Swapped correctly            
//Output: i:36 j:0

Jetzt möchte ich wissen, Warum gibt mein Code eine falsche Ausgabe?


76
2018-04-07 06:56


Ursprung


Antworten:


EDIT: Okay, verstanden.

Der erste Punkt ist, dass Sie diesen Code natürlich nicht verwenden sollten. Wenn Sie es jedoch erweitern, entspricht es:

j = j ^ (i = i ^ (j = j ^ i));

(Wenn wir einen komplizierteren Ausdruck wie foo.bar++ ^= iwäre es wichtig, dass die ++ wurde nur einmal bewertet, aber hier glaube ich, dass es einfacher ist.)

Nun ist die Reihenfolge der Auswertung der Operanden immer von links nach rechts, also erhalten wir:

j = 36 ^ (i = i ^ (j = j ^ i));

Dies (oben) ist der wichtigste Schritt. Wir haben am Ende 36 als LHS für die XOR-Operation, die zuletzt ausgeführt wird. Die LHS ist nicht "der Wert von j nachdem die RHS ausgewertet wurde ".

Die Bewertung des RHS von ^ beinhaltet den Ausdruck "eine Ebene verschachtelt", also wird es:

j = 36 ^ (i = 25 ^ (j = j ^ i));

Wenn wir dann auf die tiefste Ebene der Verschachtelung schauen, können wir beide ersetzen i und j:

j = 36 ^ (i = 25 ^ (j = 25 ^ 36));

... was wird

j = 36 ^ (i = 25 ^ (j = 61));

Die Zuordnung zu j in der RHS tritt zuerst auf, aber das Ergebnis wird dann am Ende trotzdem überschrieben, so dass wir das ignorieren können - es gibt keine weiteren Auswertungen von j vor der letzten Aufgabe:

j = 36 ^ (i = 25 ^ 61);

Dies entspricht jetzt:

i = 25 ^ 61;
j = 36 ^ (i = 25 ^ 61);

Oder:

i = 36;
j = 36 ^ 36;

Was wird:

i = 36;
j = 0;

ich denken das ist alles richtig, und es kommt zur richtigen Antwort ... Entschuldigung für Eric Lippert, wenn einige der Details über die Evaluationsreihenfolge etwas abweichen :(


76
2018-04-07 07:07



Überprüft die generierte IL und gibt verschiedene Ergebnisse aus;

Der richtige Swap erzeugt ein einfaches:

IL_0001:  ldc.i4.s   25
IL_0003:  stloc.0        //create a integer variable 25 at position 0
IL_0004:  ldc.i4.s   36
IL_0006:  stloc.1        //create a integer variable 36 at position 1
IL_0007:  ldloc.1        //push variable at position 1 [36]
IL_0008:  ldloc.0        //push variable at position 0 [25]
IL_0009:  xor           
IL_000a:  stloc.1        //store result in location 1 [61]
IL_000b:  ldloc.0        //push 25
IL_000c:  ldloc.1        //push 61
IL_000d:  xor 
IL_000e:  stloc.0        //store result in location 0 [36]
IL_000f:  ldloc.1        //push 61
IL_0010:  ldloc.0        //push 36
IL_0011:  xor
IL_0012:  stloc.1        //store result in location 1 [25]

Der falsche Swap generiert diesen Code:

IL_0001:  ldc.i4.s   25
IL_0003:  stloc.0        //create a integer variable 25 at position 0
IL_0004:  ldc.i4.s   36
IL_0006:  stloc.1        //create a integer variable 36 at position 1
IL_0007:  ldloc.1        //push 36 on stack (stack is 36)
IL_0008:  ldloc.0        //push 25 on stack (stack is 36-25)
IL_0009:  ldloc.1        //push 36 on stack (stack is 36-25-36)
IL_000a:  ldloc.0        //push 25 on stack (stack is 36-25-36-25)
IL_000b:  xor            //stack is 36-25-61
IL_000c:  dup            //stack is 36-25-61-61
IL_000d:  stloc.1        //store 61 into position 1, stack is 36-25-61
IL_000e:  xor            //stack is 36-36
IL_000f:  dup            //stack is 36-36-36
IL_0010:  stloc.0        //store 36 into positon 0, stack is 36-36 
IL_0011:  xor            //stack is 0, as the original 36 (instead of the new 61) is xor-ed)
IL_0012:  stloc.1        //store 0 into position 1

Es ist offensichtlich, dass der in der zweiten Methode erzeugte Code inkorect ist, da der alte Wert von j in einer Berechnung verwendet wird, in der der neue Wert benötigt wird.


15
2018-04-07 07:18



C # lädt j, i, j, i auf dem Stapel und speichert jede XOR Ergebnis, ohne den Stapel zu aktualisieren, also ganz links XOR verwendet den Anfangswert für j.


7
2018-04-07 07:22



Umschreiben:

j ^= i;       
i ^= j;
j ^= i;

Erweitern ^=:

j = j ^ i;       
i = j ^ i;
j = j ^ i;

Ersatz:

j = j ^ i;       
j = j ^ (i = j ^ i);

Ersetzen funktioniert nur, wenn / weil die linke Seite des ^ Operators zuerst ausgewertet wird:

j = (j = j ^ i) ^ (i = i ^ j);

Zusammenbruch ^:

j = (j ^= i) ^ (i ^= j);

Symmetrisch:

i = (i ^= j) ^ (j ^= i);

0
2017-11-21 18:29