Too much discussion of the XOR swap trick

The following post involves far too much discussion of the XOR swap trick. I suspect many readers already know some of this, so feel free to skip over some early sections if you like! If you already know what the XOR swap trick is, you can skip straight to the part where we see if it’s useful.

What does XOR mean?

XOR is short for Exclusive OR (we use the X, instead of EOR, because X is cooler). XOR has a lesser known, less cool friend, Inclusive Or (IOR).

These two names comes from an issue in English (and many other languages), where we use ‘or’ for two different purposes. The difference between these two is when someone talks about “A or B”, are you allowed both A and B, or just one or the other? In maths and computing, where we need to be more exact, we separate these two cases into XOR (you cannot have both) and IOR (you can have both).

To hopefully make this clearer, let’s consider a couple of real world examples. I decided to pick a couple of examples from the Disney World website. Let’s begin by picking one of the rules of Disney World, you cannot “harass or harm wildlife” – reasonable sounding rule! If you started kicking a duck while also insulting it, you would be both harassing and harming wildlife. This is clearly an ‘inclusive’ or, if you tried to claim you were not “harassing or harming wildlife, I’m doing both!”, you would still get kicked out of the park.

On the other hand, over in the Refreshment Corner, the “All-Beef Hot Dog Basket” comes with a “Mandarin Orange or a Small Bag of Chips”. Here, the ‘or’ is exclusive, you can have an orange, you can have chips, but you cannot have an orange and chips! No matter how much you pointed at the person being dragged out of the park for duck harassment and harming, Disney are not going to agree their rules are inconsistent.

How do we know if an ‘or’ is inclusive or exclusive? There are some general rules, but often you just have to know by context. However, because we want to be clear when using computers, we are going to use ‘XOR’ when we mean “A, or B, but not both”.

What is a logical XOR?

A logical XOR takes two true/false values and returns true when exactly one of the two is true. We can write this out as a table:

| A | B | A XOR B | |---|---|---| | false | false | false | | false | true | true | | true | false | true | | true | true | false |

One useful way to think about XOR: A XOR B is the same as asking “are A and B different?” If they are different, the result is true. If they are the same, the result is false. This will become important later.

What is the XOR bitwise operator?

In most programming languages, the ^ operator performs a bitwise XOR. This means it takes two integers, lines up their binary representations, and applies logical XOR to each pair of bits independently.

For example, let’s XOR the numbers 12 and 10:

12 = 1100
10 = 1010
----------
^ = 0110 = 6

Each column is just a logical XOR: 1 XOR 1 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, 0 XOR 0 = 0.

Bitwise XOR has two properties that matter for the swap trick:

Self-inverse: a ^ a == 0 for any value a. Every bit cancels with itself. Identity: a ^ 0 == a. XOR with zero changes nothing.

Combining these: if we compute a ^ b ^ b, the two bs cancel and we get back a. This works the other way too: a ^ b ^ a gives us b. Hold that thought.

What is the XOR swap trick?

The XOR swap trick uses those properties to swap two variables without a temporary variable. Here it is in C:

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

Let’s trace through this with a = 5 and b = 3:

| Step | Operation | a | b | |---|---|---|---| | Start | | 5 | 3 | | Line 1 | a ^= b | 5 ^ 3 = 6 | 3 | | Line 2 | b ^= a | 6 | 3 ^ 6 = 5 | | Line 3 | a ^= b | 6 ^ 5 = 3 | 5 |

After line 1, a holds a ^ b. After line 2, b holds b ^ (a ^ b) which simplifies to a (the bs cancel). After line 3, a holds (a ^ b) ^ a which simplifies to b (the as cancel). The values have been swapped, and we never needed a temporary variable.

This is a clever bit of programming, and you can find it discussed in many places online. The question is: is it actually useful? Let’s find out.

Usage 1: Swapping local variables

The most common place you might want to swap two variables is right there in a function, with local variables. So let’s write three functions and see what the compiler makes of them. First, a baseline – just return a / b:

int div_direct(int a, int b) {
  return a / b;
}

Now, a version that XOR-swaps a and b and then divides:

int div_xor_swap(int a, int b) {
  a ^= b;
  b ^= a;
  a ^= b;
  return a / b;
}

And finally, the boring version with a temporary variable:

int div_temp_swap(int a, int b) {
  int temp = a;
  a = b;
  b = temp;
  return a / b;
}

The XOR-swap and temp-swap versions should both compute b / a (since we swap before dividing). Let’s compile all three with clang -O2 on x86-64 and look at the assembly:

div_direct:
        mov     eax, edi
        cdq
        idiv    esi
        ret
div_xor_swap:
        mov     eax, esi
        cdq
        idiv    edi
        ret
div_temp_swap:
        mov     eax, esi
        cdq
        idiv    edi
        ret

The compiler has seen straight through both swaps. div_direct divides edi by esi (that is, a / b). Both div_xor_swap and div_temp_swap divide esi by edi (that is, b / a). The generated code is identical – no XOR instructions, no temporary variable, no swap at all. The compiler just tracks which value is in which register and adjusts the final division accordingly.

In practice, this is the situation for almost any use of the XOR swap trick on local variables. The compiler is perfectly capable of working out that you are swapping two values, and it will just rearrange the subsequent operations to account for that. The XOR swap trick does nothing here that the compiler would not already do for you.

Usage 2: Swapping through pointers

So what about writing a proper swap function, one that takes two pointers? Let’s try both approaches:

void swap_xor(int* a, int* b) {
  *a ^= *b;
  *b ^= *a;
  *a ^= *b;
}
void swap_temp(int* a, int* b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

Here the compiler can’t just rearrange later operations, because the function’s whole purpose is the swap itself. Let’s see what we get:

swap_xor:
        mov     eax, dword ptr [rdi]
        xor     eax, dword ptr [rsi]
        mov     dword ptr [rdi], eax
        xor     eax, dword ptr [rsi]
        mov     dword ptr [rsi], eax
        xor     dword ptr [rdi], eax
        ret
swap_temp:
        mov     eax, dword ptr [rdi]
        mov     ecx, dword ptr [rsi]
        mov     dword ptr [rdi], ecx
        mov     dword ptr [rsi], eax
        ret

The temp variable version is 4 instructions and does exactly what you would expect: load both values into registers, then write them back the other way around. Once the values are in registers, the swap is essentially free – we just store them to the opposite locations.

The XOR version is 6 instructions. It is doing genuine XOR operations, loading, storing, and reloading values. It is strictly worse. So much for saving a register.

Why didn’t the compiler optimise the XOR swap away?

With local variables, the compiler saw straight through both swaps and produced identical code. So why doesn’t it do the same thing here?

Let’s think about what happens if we call swap_temp(&x, &x) – that is, we pass the same pointer for both arguments. The function loads *a into temp, writes *b (the same value) into *a, then writes temp (the original value) back into *b. Nothing changes, which is exactly what we would expect from “swapping” something with itself.

Now consider swap_xor(&x, &x). The very first line, *a ^= *b, computes x ^ x, which is zero. That zero gets written back, and the original value is gone. The XOR swap trick destroys the data when both pointers point to the same address.

This means the two functions are not equivalent. The compiler cannot replace one with the other, because they behave differently when aliased.