Swap two variables using XOR

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.

23 Comments »

Trackbacks & Pingbacks

Pingback by Why is C++ very popular for Game Development? - Page 2 - The ProgrammersTalk Community — July 11, 2007 @ 9:19 pm
Pingback by xor swap « Blog do Lameiro — December 7, 2007 @ 8:09 pm
Pingback by First “Real” Post « erik.wiffin blogs — March 17, 2009 @ 6:37 pm

Comments

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…

Ken — April 2, 2007 @ 12:18 am
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.

Kalid — April 6, 2007 @ 12:09 pm
Hi! I think the following note will be helpful, since it highlights the properties involved in all these swappings:

http://www.cs.nott.ac.uk/~jff/papers/JFFs/JFF1.pdf

Joao F. Ferreira — June 15, 2007 @ 8:13 am
Thanks Joao, that paper is pretty interesting.

Kalid — June 15, 2007 @ 12:04 pm
Kalid,

I’ve just published a new version of my note on this. You can find it at:

http://www.joaoferreira.org/2007/07/11/swapping-the-values-of-two-variables/

Joao Ferreira — July 11, 2007 @ 8:12 am
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

zezima — November 27, 2007 @ 8:11 pm
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.

Kalid — November 27, 2007 @ 8:21 pm
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

Rich — July 17, 2008 @ 8:04 am
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
in c this can be written as x^=y^=x^=y

Anonymous — September 27, 2008 @ 5:19 am
@Anonymous: That’s right — in “slightly obfuscated” c .

Kalid — September 28, 2008 @ 11:39 am
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.

Jon Anderson — February 12, 2009 @ 7:22 pm
can i just make it like dis:
a=5
b=4
a=(a+b)-a
b=(b+a)-b
please help me…i really had a hard tym with this

lee — February 18, 2009 @ 2:41 am
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

lee — February 18, 2009 @ 2:48 am
lee — February 18, 2009 @ 2:50 am
Try this article at http://www.madanrevoor.com/c-programming/how-to-swap-two-variables-without-a-temp-variable

CoolDude — February 24, 2009 @ 11:25 am
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.

Borsuc — May 31, 2009 @ 1:13 pm
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

Anonymous — June 23, 2009 @ 6:41 am
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.

Anonymous — November 1, 2009 @ 5:22 pm
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;

Sriram — November 14, 2009 @ 9:30 pm

RSS feed for comments on this post. TrackBack URI

Have a question? Know an explanation that caused your own a-ha moment? Write about it here.