Warum schlägt das Austauschen von Werten mit XOR fehl, wenn dieses zusammengesetzte Formular verwendet wird?

76

Ich habe festgestellt, dass dieser Code zwei Zahlen ohne Verwendung einer dritten Variablen mit dem XOR- ^Operator austauscht .

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 mein Code eine falsche Ausgabe liefert.

c# swap xor Javed Akram
quelle
2
Dies wäre die gleiche Antwort wie für: stackoverflow.com/questions/3741440 oder viele der anderen in der Spalte "Verwandte". Obwohl sie C ++ sagen und dies C # ist, würden die gleichen Regeln gelten.
Daemin
8
@Daemin: Nein, die gleichen Regeln gelten nicht . Es ist undefiniertes Verhalten in C ++, aber ich glaube nicht, dass es in C # undefiniert ist.
Jon Skeet
3
@Daemin - Hier ist ein verwandter Beitrag von Eric Lippert vor zwei Tagen: stackoverflow.com/questions/5538193/… , insbesondere: "Die anderen Antworten weisen darauf hin, dass in den Programmiersprachen C und C ++ die Sprachspezifikationen nicht angegeben sind in welcher Reihenfolge Nebenwirkungen auftreten, wenn die Nebenwirkung und ihre Beobachtung innerhalb des gleichen "Sequenzpunkts" liegen, wie sie hier sind. [...] C # erlaubt diese Art von Lattitude nicht. In C # ist eine Nebenwirkung zu Es wird beobachtet, dass die linke Seite passiert ist, wenn der Code rechts ausgeführt wird. "
Kobi
2
Eines Tages möchte ich an eine Frage denken, die für Jon Skeet interessant genug ist, um über ...
David Johnstone
8
Für diejenigen, die die Frage geschlossen haben - die andere Frage befasst sich mit C, C ++, wo das Ergebnis aufgrund fehlender Sequenzpunkte undefiniert ist. Während sich diese Frage mit C # befasst, wo die Antwort gut definiert ist, sich aber von dem unterscheidet, was zu erwarten ist. Ich würde es also nicht als doppelte Frage behandeln, da die Antworten deutlich unterschiedlich sind.
Damien_The_Unbeliever

Antworten:

77

EDIT: Okay, verstanden.

Der erste Punkt ist, dass Sie diesen Code offensichtlich sowieso nicht verwenden sollten. Wenn Sie es jedoch erweitern, entspricht es:

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

(Wenn wir einen komplizierteren Ausdruck wie verwenden foo.bar++ ^= iwürden, wäre es wichtig, dass der ++nur einmal ausgewertet wurde, aber hier glaube ich, dass es einfacher ist.)

Die Reihenfolge der Auswertung der Operanden ist immer von links nach rechts. Zunächst erhalten wir also:

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

Dies (oben) ist der wichtigste Schritt. Wir haben 36 als LHS für die zuletzt ausgeführte XOR-Operation erhalten. Die LHS ist nicht "der Wert jnach der Auswertung der RHS".

Die Auswertung der RHS des ^ beinhaltet den Ausdruck "One Level Nested", also wird es:

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

Wenn wir dann die tiefste Ebene der Verschachtelung betrachten, können wir beide ersetzen iund j:

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

... was wird

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

Die Zuordnung zu jin der RHS erfolgt zuerst, aber das Ergebnis wird dann am Ende trotzdem überschrieben, sodass wir das ignorieren können - es gibt keine weiteren Auswertungen jvor der endgültigen Zuordnung:

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

Dies entspricht nun:

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

Oder:

i = 36;
j = 36 ^ 36;

Welches wird:

i = 36;
j = 0;

Ich denke , das ist alles richtig und es kommt zur richtigen Antwort ... Entschuldigung an Eric Lippert, wenn einige Details zur Bewertungsreihenfolge leicht abweichen :(

Jon Skeet
quelle
1
Die IL schlägt vor, dass genau dies geschieht.
SWeko
1
@Jon Ist dies nicht nur ein weiterer Beweis dafür, dass Sie keine Ausdrücke mit Variablen haben sollten, die Nebenwirkungen haben, es sei denn, Sie verwenden die Variable nur einmal?
Lasse V. Karlsen
8
@Lasse: Auf jeden Fall. Code wie dieser ist schrecklich.
Jon Skeet
8
Warum ist einer der größten C # -Experten mit solchen Frequenzzuständen "Sie sollten diesen Code nicht verwenden" in SO-Antworten? ;-)
Fredrik Mörk
8
@Fredrik: In diesem Fall habe ich mir den Code nicht ausgedacht. Es ist etwas anderes , wenn jemand fragt , wie man etwas erreichen kann , und ich stamme den schrecklichen Code :)
Jon Skeet
15

Überprüft die generierte IL und es werden unterschiedliche Ergebnisse ausgegeben.

Der richtige Tausch erzeugt eine einfache:

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 Tausch 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 generierte Code fehlerhaft ist, da der alte Wert von j in einer Berechnung verwendet wird, in der der neue Wert erforderlich ist.

SWeko
quelle
Ich habe die Ausgabe überprüft und es gibt unterschiedliche Ergebnisse :). Die Frage ist, warum das passiert ...
Kobi
Es ist also alle Werte Laden braucht es den gesamten Ausdruck auf den Stapel zunächst zu bewerten, dann XOR - Verknüpfung und Werte zurück in die Variablen Speichern , wie es geht (so wird es die Anfangswerte von i und j im gesamten Auswertung des Ausdrucks verwenden)
Damien_The_Unbeliever
Erklärung für die zweite IL
SWeko
1
Schade, dass der Code für einen Tausch nicht nur ist ldloc.0; ldloc.1; stloc.0; stloc.1. In C # sowieso; Es ist vollkommen gültige IL. Jetzt, wo ich darüber nachdenke, frage ich mich, ob C # die temporäre Variable aus einem Swap heraus optimieren würde.
CHao
7

C # Lasten j, i, j, iauf den Stapel und speichert jedes XORErgebnis ohne den Stapel zu aktualisieren, so dass die am weitesten links stehenden XORAnwendungen den Anfangswert für j.

C.Evenhuis
quelle
0

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 dies 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);
Wouter
quelle