Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

When I first started working a mainframe assembler programmer showed me how they swap to values without using the traditional algorithm of:

a = 0xBABE
b = 0xFADE

temp = a
a = b
b = temp

What they used to swap two values - from a bit to a large buffer - was:

a = 0xBABE
b = 0xFADE

a = a XOR b
b = b XOR a
a = a XOR b

now

b == 0xBABE
a == 0xFADE

which swapped the contents of 2 objects without the need for a third temp holding space.

My question is: Is this XOR swap algorithm still in use and where is it still applicable.

share|improve this question
29  
It's still in wide use for showing off and bad interview questions; that's about it. –  Michael Borgwardt Jan 9 '13 at 14:40
1  
Is this something like the trick: a=a+b, b=a-b, a=a-b ? –  Pieter B Jan 9 '13 at 15:13
2  
@PieterB yes they are both cases of this stackoverflow.com/questions/1826159/… –  jk. Jan 9 '13 at 15:44
    
So... You save a register but pay with 3 more instructions. I think the temp version would be faster anyway. –  Billy ONeal Jan 10 '13 at 8:03
1  
@MSalters value swap haven't been a problem in x86 from its very beginning due to xchg instruction. OTOH swapping 2 memory locations require 3 xchgs:) –  Netch Dec 19 '13 at 10:36
show 1 more comment

4 Answers

up vote 28 down vote accepted

When using xorswap there's a danger of supplying same variable as both arguments to the function which zeroes out the said variable due to it being xor'd with itself which turns all the bits to zero. Of course this itself would result in unwanted behavior regardless of algorithm used, but the behavior might be surprising and not obvious at first glance.

Traditionally xorswap has been used for low-level implementations for swapping data between registers. In practice there are better alternatives for swapping variables in registers. For example Intel's x86 has a XCHG instruction which swaps the contents of two registers. Many times a compiler will figure out the semantics of a such function(it swaps contents of the values passed to it) and can make it's own optimizations if needed, so trying to optimize something as trivial as a swap function does not really buy you anything in practice. It's best to use the obvious method unless there's a proven reason why it would be inferior to say xorswap within the problem domain.

share|improve this answer
12  
If both values are the same, then you'd still end up with the correct result. a: 0101 ^ 0101 = 0000; b: 0101 ^ 0000 = 0101; a: 0101 ^ 0000 = 0101; –  Bobson Jan 9 '13 at 14:44
1  
+1 after the edit –  GlenH7 Jan 9 '13 at 14:49
1  
What @GlenH7 said. -1 -> +1. –  Bobson Jan 9 '13 at 14:55
2  
@Chris No, at first I had written that if the values were identical as if a=10, b=10, and if you did xorswap(a,b) that would work and not zero out the variables which is false and now removed. But if you did xorswap(a, a) then a would get zeroed which I had originally meant but was being stupid. :) –  zxcdw Jan 9 '13 at 18:03
1  
It's pretty relevant in certain languages - small little dangers like that make for difficult to find bugs in the future when dealing with two pointers that somehow were set to point to the same address 100+ lines up that you don't see. –  Drake Clarris Jan 9 '13 at 19:03
show 4 more comments

My colleague reported that this is a base trick he has taught in university studying for a programmer of automated systems. Many such systems are embedded ones with limited resources and they could lack a free register to keep the temporary value; in that case, such tricky exchange (or its analog with adding and subtracting) is getting vital so still being used.

But one shall care using it that these two locations can't be identical because in the latter case it will effectively zero both values. So usually it's being limited to obvious cases like exchanging a register and a memory location.

With x86, the xchg and cmpxchg instructions satisfy the need in most cases, but RISCs generally aren't covered with them (except Sparc).

share|improve this answer
add comment

The key to the answer is in the question - "working a mainframe assembler programmer" - in the days before the compiler. When humans hunkered down with assembly instructions and hand crafted exact solutions for a particular piece of hardware (that may or may not work on another model of the same computer - issues such as the timing of hard drives and drum memory had impact on how code was written - read The Story of Mel if one feels the need to be nostalgic).

Back in these bygone days, registers and memory were both scarce and any trick to not have to beg for another byte or word of memory from the lead architect was time saved - both in writing the code and execution time.

Those days are gone. The trick of swapping two things without using a third is a trick. Memory and registers are both plentiful in modern computing and humans don't write assembly anymore. We've taught all of our tricks to our compilers, and they do a better job of it than we do. Chances are the compiler did something even better than what we would have done. In most cases, sometimes we need to write assembly in some inner bit of a tight loop for some reason... but it isn't to save a register or a word of memory.

It might be useful again if one is working in a particularly limited microcontroller, but optimizing a swap isn't likely the source of one's problem then - trying to be too clever is more likely a problem.

share|improve this answer
add comment

Will it work? Yes.

Should you use it? No.

This sort of micro-optimization would make sense if:

  • you have looked at the code the compiler generates for the straightforward way of doing this (assignment and a temporary) and decided that the XOR approach generates faster code

  • you have profiled your app, and found the cost of the straightforward approach outweighs the clarity of the code (and resulting savings in maintainability)

To the first point, unless you've done this measurement, you should be trusting the compiler. When the semantics of what you're trying to do are clear, there are a lot of tricks the compiler can do, including rearranging variable access so that the swap is not needed at all, or in-lining whatever machine level instructions provide the fastest swap for a given data type. "Tricks" such as the XOR swap make it harder for the compiler to see what you are trying to do, and thus make it less able to apply such optimizations.

To the second point, what are you gaining for the added complexity? Even if you've measured and found the XOR approach faster, is this having enough impact to justify a less clear approach? How do you know?

Finally, you should look into whether there is a standard swap function for your platform/language -- the C++ STL, for instance, provides a template swap function which will tend to be highly optimized for your compiler/platform.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.