3

I have read several sources that discuss how to swap two numbers without using a third variable. These are a few of the most relevant:

I understand why it doesn't make sense to use the described methods in most cases: the code becomes cluttered and difficult to read and will usually execute more slowly than a solution utilizing a third "temp" variable. However, none of the questions I have found discuss any benefits of the two-variable methods in practice. Do they have any redeeming qualities or benefits(historical or contemporary), or are they only useful as obscure programming trivia?

Improve this question
2
  • 2
    "In a programming interview." Commented Jul 24, 2014 at 12:31
  • 1
    Not exactly the same thing, but under certain conditions it's possible to use a linked list that contains just a single pointer in each node as a bidirectional linked list by storing pNext ^ pPrevious in this pointer entry. Then, provided you know the address of the {previous,next} node as well as the current one, you can get to the {next,previous} node with an XOR. Commented Jul 24, 2014 at 12:35

2 Answers 2

Reset to default
6

At this point it's just a neat trick. Speed-wise if it makes sense though your compiler will recognize a normal swap and optimize it appropriately (but no guarantees that it will recognize weird xoring and optimize that appropriately).

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

The compiler is probably more likely to recognize a simple swap with a temp variable as an opportunity to perform some kind of optimization.
@StriplingWarrior I think that was the point of this answer - no need to use fancy tricks, the compiler already knows about them and can recognize a simple swap through an otherwise unused temporary. But that begs the question, are there any compilers that actually make this optimization?
@MarkRansom I'm guessing most compilers use even better optimizations most of the time. For example, if you're just using a temporary variable, then the compiler can use a CPU register to store that value rather than saving it in memory. The XOR trick just adds a couple of CPU operations. Remember: "variables" exist for the sake of the programmer, and don't necessarily resemble what's happening in the compiled code.
@MarkRansom X86, at least, has a swap (xchg) instruction. I am sure xor-swap is a useful optimization on some (register starved?) chips.
2

Another strike against xor is that if one variable alias the other, xor’ing them will zero both out. Since you’ll have to check for and handle this condition, you’ll have extra code involved – probably by using the third variable method.

You could also try adding and subtracting values… except that you’d have to check for and handle overflow, which would involve more code (probably the third variable method). Multiplication and division have the same flaw, but more importantly, there’s the exquisite delight of representing fractions in binary (so this wouldn’t work in the first place).

Edit: D’oh, sorry for the thread necromancy… got so caught up in following links that I forgot to check the dates.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.