Search code examples
c#swapxor

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?

Solution

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