Too much Discussion of the XOR swap trick

Programming

Rambling

Published

March 16, 2026

What is the XOR swap trick?

The following post involves far too much discussion of the XOR swap trick. If XOR itself is unfamiliar, I have written a gentler introduction to it.

Back when I was graduating (which is longer ago than I want to admit), trick programming questions were all the rage. One of them was: “Can you swap two variables without a temporary variable?”

This question enraged me for two reasons. First, I don’t believe anyone would figure out the answer without already knowing it, so it tests whether someone knows a silly trick rather than whether they can program. Second, and more importantly to me, people often presented the answer as a wonderfully efficient way to swap two variables. As we are going to see, compilers do not agree.

So, this post will explain the XOR swap trick, then look at every place it could be useful and see what the compiler does with it. When the optimiser can understand the swap, it removes the XORs. When possible pointer aliasing prevents that, the result contains more instructions.

The swap trick relies on two facts: a ^ a == 0, and a ^ 0 == a. XORing a value with itself cancels it out, while XORing with zero changes nothing. This lets us swap two variables without a temporary variable:

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.

Amazing! We managed to swap two variables without having to copy one of them into a temporary. Memory savings and greater speeds are ours to take! Because surely it’s better to save the temporary variable… right? 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. Don’t worry if you can’t read assembly. The important thing is that the two swaps are, well, exactly the same!

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.

An important thing to realise here is that compilers don’t have clever optimisations to turn things into the XOR swap trick. They have clever optimisations to detect it and take it out!

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, it just stores them to the opposite locations.

The XOR version is 6 instructions. It is doing genuine XOR operations, loading, storing, and reloading values. That is strictly more instructions: 6 instead of 4. So much for saving a register.

Instruction counts are not timings. Modern CPUs make microbenchmarking code this small extremely difficult, so I am not going to claim an exact speed difference. We don’t need one: the promised saving has failed to appear, and the XOR version contains more instructions.

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. It has to faithfully emit the XOR operations, reloading from memory after each store, because each write through one pointer might be changing the value that the other pointer sees.

Except, in C we can tell the compiler that two pointers will never alias, using the restrict keyword:

void swap_xor_restrict(int* restrict a, int* restrict b) {
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

With restrict, we are promising that a and b point to different memory. Now the compiler knows the aliasing case cannot happen, and:

swap_xor_restrict:
    mov   eax, dword ptr [rsi]
    mov   ecx, dword ptr [rdi]
    mov   dword ptr [rsi], ecx
    mov   dword ptr [rdi], eax
    ret

We are back to 4 instructions – just loads and stores, no XOR in sight. The compiler has optimised the XOR swap into exactly the same code as the temp variable version. The trick has, once again, bought us nothing.

So, why do people care about the XOR swap trick?

At this point, the XOR swap trick has either produced identical code or added instructions in every case we have tried. So why does it come up at all?

Part of the answer is that it looks clever. It is the kind of thing you can write on a whiteboard and puzzle someone with for thirty seconds, which gives it a life as an interview question and a “did you know” curiosity.

But there is a kernel of a genuine use case, which becomes clearer if we think in terms of assembly rather than C. Imagine you are hand-writing assembly code and you need to swap two values that are already in registers. If you have a spare register, the obvious approach is three moves:

move  $t2, $t0    # t2 = t0 (save)
move  $t0, $t1    # t0 = t1
move  $t1, $t2    # t1 = saved value

That is three instructions, and it requires a register you are not using for anything else. XOR swap is also three instructions, and requires no spare register:

xor   $t0, $t0, $t1    # t0 = t0 ^ t1
xor   $t1, $t1, $t0    # t1 = t1 ^ (t0 ^ t1) = original t0
xor   $t0, $t0, $t1    # t0 = (t0 ^ t1) ^ original t0 = original t1

So if you have a spare register, there is no reason to use XOR swap — both versions use three instructions, and the moves are clearer. XOR swap might help when you are genuinely out of spare registers and would otherwise have to spill a value to memory.

So, what about everyone’s (no-one’s?) favourite processor architecture, x86 and its sequel, x86-64? It has an XCHG instruction, which swaps two registers directly. We don’t need any of this.

MIPS has 32 general-purpose registers, and AArch64 has 31. It is very, very unlikely that every usable register is already holding a value you need, but… maybe they are all full. In that case, XOR swap is a genuine option: three register-to-register XOR instructions, no memory access and no spare register needed.

Perhaps an older processor with fewer registers gives the trick a better chance? The Z80 is a tempting example: it has very few registers, and many operations are restricted to the accumulator. However, the Z80’s XOR instruction can only write to the accumulator (A), so XOR B means A ^= B, and there is simply no single instruction for B ^= A. The three-step XOR swap does not work on Z80 between arbitrary registers.

So this might have been useful in the 1980s, or might still be useful vanishingly rarely in hand-written assembly when there really is no space. In practice, it is only useful for cute interview questions and as a curiosity.

Are there other XOR tricks?

Turns out this wasn’t the only way XOR terrorised graduates with incredibly mean interview questions. Another favourite: given a list where every value appears exactly twice except one, XOR all the values together and the duplicates cancel out, leaving the unique element.

int find_unique(int* values, int n) {
    int result = 0;
    for (int i = 0; i < n; i++) {
        result ^= values[i];
    }
    return result;
}

For {4, 7, 2, 7, 4}, this computes 4 ^ 7 ^ 2 ^ 7 ^ 4. The two 4s cancel, the two 7s cancel, and we are left with 2. One pass through the data, no extra storage, no sorting, no hash table.

If you don’t know anything else about the values in the list, this really is very clever. I don’t know of any other way to do it anywhere near as efficiently — it is O(n) time and O(1) space, which is hard to beat. I also can’t think of any reason you would actually want to do this. But you certainly can.

There are a number of other XOR tricks out there — XOR linked lists, XOR in hash functions — but this post has already met its quota of entirely too much too much XOR.