Why does swapping values with XOR fail when using

问题:

I found this code to swap two numbers without using a third variable, using the XOR ^ 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

Now I changed the above code to this equivalent code.

My 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

Now, I want to know, Why does my code give incorrect output?

回答1:

EDIT: Okay, got it.

The first point to make is that obviously you shouldn't use this code anyway. However, when you expand it, it becomes equivalent to:

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

(If we were using a more complicated expression such as foo.bar++ ^= i, it would be important that the ++ was only evaluated once, but here I believe it's simpler.)

Now, the order of evaluation of the operands is always left to right, so to start with we get:

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

This (above) is the most important step. We've ended up with 36 as the LHS for the XOR operation which is executed last. The LHS is not "the value of j after the RHS has been evaluated".

The evaluation of the RHS of the ^ involves the "one level nested" expression, so it becomes:

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

Then looking at the deepest level of nesting, we can substitute both i and j:

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

... which becomes

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

The assignment to j in the RHS occurs first, but the result is then overwritten at the end anyway, so we can ignore that - there are no further evaluations of j before the final assignment:

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

This is now equivalent to:

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

Or:

i = 36;
j = 36 ^ 36;

Which becomes:

i = 36;
j = 0;

I think that's all correct, and it gets to the right answer... apologies to Eric Lippert if some of the details about evaluation order are slightly off :(

回答2:

Checked the generated IL and it gives out different results;

The correct swap generates a straightforward:

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]

The incorrect swap generates this 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

It's evident that the code generated in the second method is incorect, as the old value of j is used in a calculation where the new value is required.

回答3:

C# loads j, i, j, i on the stack, and stores each XOR result without updating the stack, so the leftmost XOR uses the initial value for j.

回答4:

Rewriting:

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

Expanding ^=:

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

Substitute:

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

Substitute this only works if/because the left hand side of the ^ operator is evaluated first:

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

Collapse ^:

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

Symmetrically:

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