Why is "a^=b^=a^=b;" different from "a^=b; b^=a; a^=b;"?

Question

I tried some code to swap two integers in Java without using a 3rd variable, using XOR.

Here are the two swap functions I tried:

package lang.numeric;

public class SwapVarsDemo {

    public static void main(String[] args) {
        int a = 2984;
        int b = 87593;
        swapDemo1(a,b);
        swapDemo2(a,b);
    }

    private static void swapDemo1(int a, int b) {
        a^=b^=a^=b;
        System.out.println("After swap: "+a+","+b);
    }

    private static void swapDemo2(int a, int b) {
        a^=b;
        b^=a;
        a^=b;
        System.out.println("After swap: "+a+","+b);
    }

}

The output produced by this code was this:

After swap: 0,2984
After swap: 87593,2984

I am curious to know, why is this statement:

        a^=b^=a^=b;

different from this one?

        a^=b;
        b^=a;
        a^=b;

Answer 1

The issue is the order of evaluation:

See JLS section 15.26.2

First, the left-hand operand is evaluated to produce a variable. If this evaluation completes abruptly, then the assignment expression completes abruptly for the same reason; the right-hand operand is not evaluated and no assignment occurs.

Otherwise, the value of the left-hand operand is saved and then the right-hand operand is evaluated. If this evaluation completes abruptly, then the assignment expression completes abruptly for the same reason and no assignment occurs.

Otherwise, the saved value of the left-hand variable and the value of the right-hand operand are used to perform the binary operation indicated by the compound assignment operator. If this operation completes abruptly, then the assignment expression completes abruptly for the same reason and no assignment occurs.

Otherwise, the result of the binary operation is converted to the type of the left-hand variable, subjected to value set conversion (§5.1.13) to the appropriate standard value set (not an extended-exponent value set), and the result of the conversion is stored into the variable.

So your expression does:

a^=b^=a^=b;

1. evaluate a
2. evaluate b^=a^=b
3. xor the two (so the a in step one does not have ^=b applied to it yet)
4. store the result in a

In other words, your expression is equivalent to the following java code:

    int a1 = a;
    int b2 = b;
    int a3 = a;
    a = a3 ^ b;
    b = b2 ^ a;
    a = a1 ^ b;

You can see that from the disassembled version of your method:

  private static void swapDemo1(int, int);
    Code:
       0: iload_0       
       1: iload_1       
       2: iload_0       
       3: iload_1       
       4: ixor          
       5: dup           
       6: istore_0      
       7: ixor          
       8: dup           
       9: istore_1      
      10: ixor          
      11: istore_0  

Answer 2

Because a ^= b ^= a ^= b; is parsed like:

a ^= (b ^= (a ^= b));

Which can be reduced to:

a ^= (b ^= (a ^ b));

So b will have the value b ^ (a ^ b) and finally a will be a ^ (b ^ (a ^ b).

Answer 3

This is very similar to an entry in Bloch and Gafter's Java Puzzlers book, see Chapter 2, puzzle 7 ("Swap Meat"). I can't improve on it.

The explanation in the solution is:

This idiom was used in the C programming language and from there made its way into C++ but is not guaranteed to work in either of these languages. It is guaranteed not to work in Java. The Java language specification says that operands of operators are evaluated from left to right [JLS 15.7]. To evaluate the expression x ^= expr, the value of x is sampled before expr is evaluated, and the exclusive OR of these two values is assigned to the variable x [JLS 15.26.2]. In the CleverSwap program, the variable x is sampled twice—once for each appearance in the expression—but both samplings occur before any assignments. The following code snippet describes the behavior of the broken swap idiom in more detail and explains the output that we observed:

The code referenced in the quote above is:

// The actual behavior of x ^= y ^= x ^= y in Java
int tmp1 = x;     // First appearance of x in the expression
int tmp2 = y;     // First appearance of y
int tmp3 = x ^ y; // Compute x ^ y
x = tmp3;         // Last assignment: Store x ^ y in x
y = tmp2 ^ tmp3;  // 2nd assignment: Store original x value in y
x = tmp1 ^ y;     // First assignment: Store 0 in x

Answer 4

Check the operator precedence (ref: http://introcs.cs.princeton.edu/java/11precedence/ resulting from searching for java operator precedence). A reference to the Oracle documentation appears here (http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html), though it is a bit dense).

In particular, ^= is processed from right to left (not left to right)

Answer 5

I do not have enough reputation points to comment on Nathan's answer.

@Nathan Hughes response talking about the Java Puzzlers book is spot on, and his answer points to some insights that does allow you to do this in 1 line. Though not as elegantly as the OP's question.

As Nathan points out:

In the CleverSwap program, the variable x is sampled twice—once for each appearance in the expression—but both samplings occur before any assignments

As well as using https://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html as a guide, you can do this in 1 line with:

a = ( b = (a = a ^ b) ^ b) ^ a;

The key being the assignment of the a variable value as part of the first XOR ensuring that you keep that on the left side of the second XOR (see the jls link above, for a good example of assignment in the left hand operand). Similarly, setting the b variable with the results of the second XOR, again keeping to the left of the final XOR.

Answer 6

Second variant is equal to

a=a^(b^(a^b));