As programmers, we know that we can swap two variables by using a temporary variable. That’s fairly simple and intuitive: given two variables (x and y) that you want to swap, you store x in a temporary variable z, copy y to x, then finally copy z (the temporary) to y. But I learned recently (in my compiler’s course) that you can swap two variables without allocating a temporary variable, by using three xor operations. Here’s a little C program that demonstrates that idea:

# include<stdio.h>
void
swap(int *x, int *y)
{
     *x ^= *y;
     *y ^= *x;
     *x ^= *y;
}

int
main(int argc, char *argv[])
{
    int x = 123;
    int y = 234;
    printf("x=%d;y=%d\n", x, y);
    swap(&x, &y);
    printf("x=%d;y=%d\n", x, y);
}

./xor-swap
x=123;y=234
x=234;y=123

Neat, right?! But why would you ever want to take this approach? Especially if the underlying CPU instructions are more expensive with the xor approach. That is, the typical process for swapping two variables consists of 3 MOV instructions and the total number of cycles is 3 — one cycle per MOV instruction. Whereas 3 XOR instructions takes 9 cycles (3 cycles per instruction).

Well, one explanation is that compiler writer is making a tradeoff: we’re sacrificing CPU cycles but in return we free up a register, which is especially important for the register allocator. In other words, we’re reducing register allocation pressure.

Anyways, the last thing I want to demonstrate for you (and really, for myself) is to see 3 XOR operations at the binary level

XOR at the binary level

Although the code (above) proves that we can swap two variables using three XOR operations without a temporary variable, I wanted to actually carry out the XOR operations at the binary level to see for myself (cause seeing is believing, right?)

For the example below, assume that we have two registers ebx (1101)and eax (0001).

First operation – xor %ebx, %eax

1101
0001
====
1100

The xor operation yields 1100 and is then store into ebx.

Second operation – xor %eax, ebx

0001
1100
====
1101

This operation yields 1101 which is then stored eax.

Third operation – xor %ebx, %eax

1100
1101
====
0001

And hooray — the final xor yields: 0001.

References

http://www.asciitable.com
https://c9x.me/x86/html/file_module_x86_id_330.html