Swap two variables using XOR

Get the Math, Better Explained eBook and turn Huh? to Aha!

Most people would swap two variables x and y using a temporary variable, like this:

tmp = x
x = y
y = tmp

Here’s a neat programming trick to swap two values without needing a temp:

x = x xor y
y = x xor y
x = x xor y

Don’t believe me? Try it out – write in any initial value for x and y:

It almost seems like magic – the the same statement is repeated 3 times and voila – the values magically swap? Let’s take a closer look.

How it works

To understand this trick, break the statements into unique values:

x1 = x xor y
y1 = x1 xor y
x2 = x1 xor y1

According to our code, x2 should have y’s original value. Let’s work out the details for the last step:

x2 = x1 xor y1
x2 = x1 xor (x1 xor y)   // replace y1
x2 = (x1 xor x1) xor y   // regroup parenthesis - order does not matter for XOR
x2 = 0 xor y             // a xor a => 0
x2 = y                   // 0 xor a => a; x2 now has y's original value

Wow – x2 really does equal y! The swap happened. Now let’s try it out for y1:

y1 = x1 xor y
y1 = (x xor y) xor y
y1 = x xor (y xor y)
y1 = x xor 0
y1 = x                  // y1 == x's original value

And tada the trick worked again. x2 and y1 have the swapped answers.

Intuitive Understanding

Ok, sure, the boolean algebra works out great — but that’s not satisfying. I want to understand it deep down and have it make sense, not be some artifact of the properties of XOR. Let’s take another look:

1:   x = x xor y
2:   y = x xor y
3:   x = x xor y

On line 1 we combine x and y (using XOR) to get this “hybrid” and we store it back in x. XOR is a great way to save information, because you can remove it by doing an XOR again.

So, this is exactly what we do on line 2. We XOR the hybrid with y, which cancels out all the y information, leaving us only with x. We save this result back into y, so now they have swapped.

On the last line, x still has the hybrid value. We XOR it yet again with y (now with x’s original value) to remove all traces of x out of the hybrid. This leaves us with y, and the swap is complete!

Would you really use this?

No way. This is a cool trick, but don’t write this as an actual swap function. If you have to debug it in 6 months you’ll be in for some fun. Let me show you why:

Suppose x and y are pointers or references to objects, and both point to the same location. We’d expect our swapping function to just switch the values around, with no net change, right?

Well, take a look at what happens if we expand out line 1:

x = x xor y
x = x xor x  // x and y are equal
x = 0

Wow! So x becomes 0 right at the get-go. That’s ok by itself, but because x and y are at the same location, we just made y zero as well! We’ve lost the original values, a problem known as aliasing: changing one variable has an indirect effect on another.

So, would you have caught this bug? I wouldn’t have, and it would have been a nightmare figuring out why an innocuous swap function was causing data loss. Cute tricks like these can be pretty dangerous. As Brian Kernighan said:

Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.

This applies so well here – we wrote the code pretty much as cleverly as we could :). So, treat this as an intellectual exercise that brings up a few points:

  • XOR is a great way to combine information and later extract it. XOR-based encryption uses this technique. Also, XOR can combine N items together, not just 2.
  • There are new ways to perform even the simplest operations.

Even more hairy details

Now, how does this work on a CPU-level?

The computer actually has an implicit “temp” variable that stores intermediate results before writing them back to a register. For example, if you add 3 to a register (in machine-language pseudocode):

ADD 3 A  // add 3 to register A

The ALU (Arithmetic Logic Unit) is actually what executes the instruction 3+A. It takes the inputs (3,A) and creates a result (3 + A), which the CPU then stores back into A’s original register. So, we used the ALU as temporary scratch space before we had the final answer.

We take the ALU’s implicit temporary data for granted, but it’s always there. In a similar way, the ALU can return the intermediate result of the XOR in the case of x = x xor y, at which point the CPU stores it into x’s original register.

Because we aren’t used to thinking about the poor, neglected ALU, the XOR swap seems magical because it doesn’t have an explicit temporary variable. Some machines have a 1-step exchange XCHG instruction to swap two registers.

Further reading:

Kalid Azad loves sharing Aha! moments. BetterExplained is dedicated to learning with intuition, not memorization, and is honored to serve 250k readers monthly.

Enjoy this article? Try the site guide or join the newsletter:
Math, Better Explained is a highly-regarded Amazon bestseller. This 12-part book explains math essentials in a friendly, intuitive manner.

"If 6 stars were an option I'd give 6 stars." -- read more reviews

36 Comments

  1. Note that in portable C (that is, according to, say, the 1999 C standard), this only works for unsigned integral types. Obviously it won’t work for floating point or pointer or struct/union types. (Portably — if you don’t care about machine-specific code, you could convert pointers to integers on many platforms and it’ll just do what you want. But it’s not guaranteed to work everywhere.)

    But also, under some (rare, but allowed) non-2s-complement signed integer representations, an xor might result in a “negative zero” that can be converted to a normal zero before continuing, resulting in the wrong sign bit setting on an output value…

  2. Wow, thanks for the details Ken! Yeah, I imagine there are all sorts of nasty side effects when using a trick like this. Appreciate the background info.

  3. there is another way, tho i doubt if it’s faster,

    a=10;
    b=15;

    a=a+b;//a=25 b=15
    b=a-b; //a=25 b=10
    a=a-b; //a=15 b=10, swapped

  4. Hi zezima, thanks for the info! That’s a neat trick too — you “combine” a and b in a similar way, and extract them as well.

    One thing to watch out for is arithmetic overflow.

  5. I followed you right through to the pointer Caveat. If both point to the same address it should still work…

    x=1234
    y=1234

    x=x xor y -> x = 1234 xor 1234 -> x = 0
    y=x xor y -> y = 0 xor 1234 -> y = 1234
    x=x xor y -> x = 0 xor 1234 -> x = 1234

  6. Hi Rich, good question.

    When using pointers to the same location, when you do the first step (x = x xor y) => 0 you also set y to 0 as well since it’s at the same location. In this case, you’ve lost the value 1234 — x and y were sharing the same location and it was overwritten with 0.

    Hope this helps.

  7. Pretty much any compiler ever will substitute the standard swap for a single exchange instruction. This means the extra variable never gets made (unless it is used later on), and the swap is only one instruction. The triple xor is not recognized as a swap (and can’t be, since the result is different when they are equal), so it is slower in the end, as well as harder to understand.

  8. can you please reconstruct my program…i am trying to retrieved the nth perfect number..this are my codes:
    int no,you=6,div=1,they=0,her=0,as;
    getch(); //the if statement will be executed if menu no. 3 is chosen
    if(opt==3){
    system(“color 33″);
    cout>no;
    while(her

  9. There’s no reason why it wouldn’t work with floating point numbers, because they are just 1s and 0s as well.

    This technique will swap the BITS, and everything made with BITS will work.

    Sure you’ll first have to have a way to access float’s bits directly with XOR.

    There’s nothing magical about float. Just bits that, together in a “special” format, represent some value. The XOR trick does not need to know the format, it just swaps the bits. (you could make your own format if you want, encryption for example, or compression, etc… and it would still work)

    Also for the pointer-to-the-same-location case, this trick will also work. Operating directly on the pointer data is not a good concept by itself when doing computations — because the compiler will not optimize it in registers. If you access the same memory subsequently it’s better to use a temporary variable in C, so the compiler can make register optimizations (put it in registers, calculate on it, then put it in memory).

    In this case it would work, since x and y would be on two registers or temporary variables.

  10. Hi Kalid,
    In response to Rich you said the following:

    ///////////////////
    Hi Rich, good question.

    When using pointers to the same location, when you do the first step (x = x xor y) => 0 you also set y to 0 as well since it’s at the same location. In this case, you’ve lost the value 1234 — x and y were sharing the same location and it was overwritten with 0.

    Hope this helps.

    Kalid — July 17, 2008 @ 12:55 pm
    //////

    I’m not able to understand why would pointer y change when pointer x changes. I think you meant
    (*y) and (*x). Please Clarify.

    Thanks.

    RM

  11. Well I’m not getting one single exchange instruction… at least in debugging mode. This is what I see in my VC++ 6 dissassembly window:

    45: a.i ^= b.i;
    00401450 mov edx,dword ptr [a]
    00401453 xor edx,dword ptr [b]
    00401456 mov dword ptr [a],edx
    46: b.i = a.i^b.i;
    00401459 mov eax,dword ptr [a]
    0040145C xor eax,dword ptr [b]
    0040145F mov dword ptr [b],eax
    47: a.i ^= b.i;
    00401462 mov ecx,dword ptr [a]
    00401465 xor ecx,dword ptr [b]
    00401468 mov dword ptr [a],ecx
    48:
    49: t = y;
    0040146B mov edx,dword ptr [y]
    0040146E mov dword ptr [t],edx
    50: y = x;
    00401471 mov eax,dword ptr [x]
    00401474 mov dword ptr [y],eax
    51: x = t;
    00401477 mov ecx,dword ptr [t]
    0040147A mov dword ptr [x],ecx

    ‘a’ and ‘b’ are what I call “flints,” a union containing a float and int.

  12. Hey guys, what about swaping variables contains string values? All of your solutions will suck… Try this and swap integer or string without third variable… Happy Sensible Coding..

    $v = ‘sriram’;
    $u = ‘lakshmi’;

    $v .= $u;
    $u = substr($v,0,(strlen($v) – strlen($u)));
    $v = substr($v,(strlen($v) – strlen($u)-1), strlen($v));

    echo ‘u = ‘ . $u .”;
    echo ‘v = ‘ . $v;

  13. The shortest I’ve found that works in ECMAscript is:
    x^=y^=x;y^=x;

    @Anonymous, this doesn’t seem to work in ECMAscript.
    y^=x^=y^=x;

    Anyone know why not?
    I think, perhaps, it should.

  14. For all of the people who are wondering about x ^= y ^= x ^= y, this causes undefined behaviour because you are modifying the same variable (x) twice in between sequence points (ie. You can’t modify a variable twice in the same statement).

  15. Have to comment on “suppose x and y are pointers or references to objects, and both point to the same location” allegedly leading to problems of both becoming zero. This is not correct if x and y are pointers (at least in C). Pointers are just values and can safely be swapped this way. I think what you mean to say is that you would run into problems if x is a reference to y (or vice-versa) because in that case x is an alias for y and if you change x then you also change y. But if x and y are pointers, even if they point to the same thing, they are quite independent and you can safely swap using xor.

  16. a=10,b=20
    a=a+b=30
    b=a-b=30-20=10;
    a=a-b=30-10=20;
    same can be done using *and/operator as given below
    a=a*b=200;
    b=a/b=200/10=20;
    a=a/b=200/20=10;
    hence the values are swapped a=20 and b=10

  17. This came up as an interview question, and I was able to think out the A+B, A-B, A-B algorithm. Alas, this algorithm would fail if A+B overflows.

    The XOR swap would be disastrous if the data are the same, since the XOR operation asks, “Are they different?” It would be wise to check equality of A and B and avoid the swap if necessary. This could be done with another XOR operation…

    On the other hand, the hardware is designed to swap, and the compilers will optimize the temp swap!! :D

Your feedback is welcome -- leave a reply!

Your email address will not be published.

LaTeX: $$e=mc^2$$