Swapping two variables with XOR instruction

Matt Chung

May 1, 2020

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 (above) code 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

Third operation - xor %ebx, %eax

1100
1101
===
0001

References

xor quiz