Why does swapping values with XOR fail when using this compound form?
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?
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 :(
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.
C＃将j ， i ， j ， i加载到堆栈上，并存储每个XOR结果而不更新堆栈，因此最左边的XOR使用j的初始值。
上一篇: 用XOR交换两个变量