Trick code; dangerous code; triple XOR swap

[btiffin]

It has been said; You can't swap two variables without using a third. Well you can, but you have to be careful.

Normally you would have something like (using C for the example)

int i, j, t;

i = 10; j = 23;

/* Swap i and j using a nice safe temporary */
t = i;
i = j;
j = t;

Well, the magc of XOR lets you do

int i, j;

i = 10; j = 23;

/* Swap i and j using the very unsafe triple XOR trick */
i ^= j;
j ^= i;
i ^= j;

Read that as i equals i XOR j; j equals j XOR i; i equals i XOR j;

Who can think of when that trick breaks? I'll give you a clue.

int i, j, *x, *y;

i = 10; j = 23; x = &i; y = &j;

*x ^= *y;
*y ^= *x;
*x ^= *y;

And the really big clue; what if x = &i and y = &i; (Both x and y point to i). What will happen to the contents of i after the triple XOR? The first XOR in particular.

This trick needs to be wrapped in a test

if (x != y) { ... }

So while a programmer looking for bare-metal efficiency may be lured by the triple XOR swap and not needing a temp; there is an extra test for every swap, so the version using a temp will probably be quicker and more efficient in general use. (But it can be fun informing an instructor if you ever hear them say "You can't swap two variables without using a third")

Cheers,
Brian Tiffin

[ericfourfour]

Please use code tags. Especially in a tutorial.

[md]

This also doesn't fit well with things like classes or complicated structures. Sure you *could* do it... but a temporary variable is quicker and easier.

[btiffin]

re code tags; From now on yes, thanks for the heads up.

But this was not really meant as a tutorial. The triple XOR trick will work for any language (that supports bit-wise exclusive or) and it always has the same problem. If you are "xor swapping" elements through two pointers and they happen to point at the same address, you zero out the data. It was meant as a warning that "cool" code is sometimes not as good as readable "standard" code. Sometimes the cool code can hold unseen gotchas.

Cheers,
Brian Tiffin

[Hikaru79]

I could be wrong, but this [a temporary swapping variable] seems like exactly the sort of thing a good modern compiler would optimize out of existence. It's almost always better to leave silly minor things like this to the compiler's best judgment.

Which, I guess, was your point all along

[Euphoracle]

Perhaps we need a thread for "Code you never thought of" or similar, seeing as this isn't really a tip, nor a tutorial, it's more of a "Hey, this will actually work, did you know that?"

[BigBear]

I am confused is XOR a command in a language. Can this be done in turing? Please elaberate.

[chrisbrown]

@BigBear:

Turing:

put 5 xor 3

5 in binary is 101.
3 in binary is 011.

By xoring each pair of bits, we get:
1 xor 0 = 1
0 xor 1 = 1
1 xor 1 = 0

110 = 6, and this is what turing should show in the above case.

[cyberfish]

This is really bad in terms of performance on modern CPUs, because

1)
the branching stalls instruction pipelines.

2)
it is impossible to parallelize those three xor instructions because they all depend on the result of a previous instruction.

In comparison, assuming the variables are in CPU's L1 cache, memory copy/loads are virtually free.

Quote:

I could be wrong, but this [a temporary swapping variable] seems like exactly the sort of thing a good modern compiler would optimize out of existence. It's almost always better to leave silly minor things like this to the compiler's best judgment.

I don't see how it can be done more efficiently without using a temp variable?

I agree that low-level optimizations should be the job of compilers, though.