Why does swapping values with XOR fail when using this compound form?

Question

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?

It would be the same answer as given for: http://stackoverflow.com/questions/3741440 or many of the others in the Related column. Even though they say C++ and this is C#, the same rules would apply. — Dominik Grabiec, Apr 07 '11 at 07:00
@Daemin: No, the same rules *don't* apply. It's undefined behaviour in C++, but I don't believe it's undefined in C#. — Jon Skeet, Apr 07 '11 at 07:05
@Daemin - Here's a related post by Eric Lippert, just two days ago: http://stackoverflow.com/questions/5538193/why-does-p-p-a-give-strange-results/5539496#5539496 , specifically: "The other answers are pointing out that in the C and C++ programming languages, the language specifications do not specify in what order side effects appear to happen if the side effect and its observation are within the same "sequence point", as they are here. [...] C# does not permit that sort of lattitude. In C#, a side effect to the left is observed to have happened by the time that code to the right executes." — Kobi, Apr 07 '11 at 07:08
@JonSkeet & @Kobi Point taken, I assumed that the same sort of undefined order of side effect within a sequence point would be present in C# as in C & C++. I guess then the expression should work if it is bracketed appropriately. Needless to say using the XOR swap trick is not a wise thing to do in modern times. — Dominik Grabiec, Apr 07 '11 at 07:41
Some day I want to think of a question that is interesting enough for Jon Skeet to tweet about... — David Johnstone, Apr 07 '11 at 08:57
For those who closed the question - the other question deals with C, C++ where the result is undefined because of a lack of sequence points. Whereas this question deals with C#, where the answer is well defined, but different to what may be expected. So I wouldn't treat it as a duplicate question, because the answers are distinctly different. — Damien_The_Unbeliever, Apr 07 '11 at 12:12

Jon Skeet · Accepted Answer · 2011-04-07T07:22:29.010

78

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 :(

edited Apr 07 '11 at 07:22

answered Apr 07 '11 at 07:07

Jon Skeet

1,421,763
867
9,128
9,194

@Jon Skeet: Thanks, Now it is clear to me. +100 Great Answer :) – Javed Akram Apr 07 '11 at 07:28
So, in conclusion, this will work: `j = (i ^= j ^= i) ^ j;`, which is about the same, without the leftmost `j`. – Kobi Apr 07 '11 at 07:28
1

The IL suggests that this is exactly what happens. – SWeko Apr 07 '11 at 07:30
1

@Jon Isn't this just another way of proving that you shouldn't have expressions with variables that have side-effects, unless you only use the variable once? – Lasse V. Karlsen Apr 07 '11 at 07:35
8

@Lasse: Absolutely. Code like this is horrible. – Jon Skeet Apr 07 '11 at 07:38
8

Why is it that one of the greatest C# experts around with such frequency states *"you should not use this code"* in SO answers? ;-) – Fredrik Mörk Apr 07 '11 at 07:43
8

@Fredrik: In this case I didn't come up with the code to start with. It's somewhat different when someone asks how you can achieve something and I *originate* the horrible code :) – Jon Skeet Apr 07 '11 at 07:52

SWeko · Answer 2 · 2011-04-07T07:33:33.080

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.

I checked the output and it gives different results `:)`. The question is why that happens... — Kobi, Apr 07 '11 at 07:23
So it's loading all of the values it needs to evaluate the whole expression onto the stack first, then xoring and saving values back into the variables as it goes (so it will be using the initial values of i and j throughout evaluating the expression) — Damien_The_Unbeliever, Apr 07 '11 at 07:23
It's a pity the code for a swap isn't just `ldloc.0; ldloc.1; stloc.0; stloc.1`. In C# anyway; it's perfectly valid IL. Now that i think about it...i wonder whether C# would optimize the temp variable out of a swap. — cHao, Apr 07 '11 at 21:34

score 7 · Answer 3 · answered Apr 07 '11 at 07:22

7

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.

answered Apr 07 '11 at 07:22

C.Evenhuis

25,996
2
58
72

score 0 · Answer 4 · answered Nov 21 '17 at 18:29

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);

Why does swapping values with XOR fail when using this compound form?

4 Answers4

Linked

Related