Why does using this compound form replace the values ​​with XOR?

Question

I found this code to replace two numbers without using a third variable using the XOR ^ operator.

The 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 have changed the above code to this equivalent code.

My code is:

 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 is my code giving the wrong output?

Answer 1

EDIT: Alright, got it.

The first thing to do is that you should not use this code anyway. However, with its expansion, it becomes equivalent:

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

(If we were to use a more complex expression like foo.bar++ ^= i , it would be important for ++ evaluated only once, but here I find it easier.)

Now the evaluation order of operands is always from left to right, so for starters we get:

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

This (above) is the most important step. We ended up with 36 as LHS for the last XOR operation. LHS is not a " j value after RHS assessment".

The RHS of ^ evaluation includes a “one-level” expression, so it becomes:

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

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

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

... which becomes

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

Assignment j to RHS is first assigned, but the result is still overwritten at the end, so we can ignore this: there are no further estimates of j until the final assignment:

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

Now this is equivalent to:

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

Or:

 i = 36; j = 36 ^ 36; 

What will happen:

 i = 36; j = 0; 

I think that everything is correct, and he comes up with the correct answer ... apologize to Eric Lippert if some details about the evaluation order are slightly turned off :(

Answer 2

Checked the generated IL and gave different results;

A correct swap creates simply:

 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] 

An 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 

Obviously, the code generated in the second method is used because the old value of j is used in the calculation where a new value is required.

Answer 3

C # loads j , i , j , i onto the stack and saves every XOR result without updating the stack, so the leftmost XOR uses the initial value for j .

Answer 4

Rewriting:

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

Extension ^= :

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

Replacement:

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

Replace this only works if /, because the left 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);