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:

## Leave a Reply

44 Comments on "Swap two variables using XOR"

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.

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

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.

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.

If x and y are pointers to the same value, then you’re only ‘swapping’ one thing, which is nonsensical?? It’s like say I’m going to swap 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…

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.

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

Thanks Joao, that paper is pretty interesting.

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/

[…] void swap (int& a, int& b) { a ^= b; // a = a XOR b b ^= a; // b = b XOR a a ^= b; // a = a XOR b } Why does it work? Here is one that explains it well: Swap two variables using XOR | BetterExplained I found another article on the same technique, along with two other techniques. However, I caution you to read the comments that follow it: 3 ways to swap variables without temp variable « Stream As the betterexplained.com article mentions, there is an XCHG instruction on some machines that allows you to swap two registers without using multiple XOR instructions. The important thing: be careful when using such unusual techniques. You never know how a program can be affected by a compiler, an assembler or libraries that are linked it. Only use it if absolutely necessary or if you merely wish to play with it in a small program. Back on-topic, those were examples of using bitwise operations to increase efficiency. Multiplication and division by 2 is fairly simple too when you only need to worry about integers. All that is required is knowledge of what operators that bit shifts use in your specific programming language, if the operation is supported in your programming language (Visual Basic does not support bit shifts natively). In C/C++ and Java, the operator is "<<" for a left shift (SHL/SAL in ASM) and ">>" for a right shift (SHR/SAR in ASM – which one is used can depend upon signedness of a value except in Java where all integers are signed integers). The bottom line: ASM is useful and the ASM ways that were used for efficiency are still quite useful at times. __________________ […]

[…] E aí pronto, suas variáveis estão invertidas. Pode acreditar (ou ler uma explicação bem mais detalhada). Legal né? […]

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

in c this can be written as x^=y^=x^=y

@Anonymous: That’s right — in “slightly obfuscated” c :).

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.

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

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

Try this article at http://www.madanrevoor.com/c-programming/how-to-swap-two-variables-without-a-temp-variable

[…] http://betterexplained.com/articles/swap-two-variables-using-xor/ […]

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.

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

Exactly, that’s what I am confused about too. Swapping the pointers is not same as swapping the value at pointed address.

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.

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.

[…] 1.Swapping in C, C++, and Java 2. Swap two variables using XOR Tags: algo 2010年底总结与展望 No comments yet. Cancel […]