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?

Community
  • 1
  • 1
SemperMelior
  • 51
  • 1
  • 6
  • 2
    "In a programming interview." – j_random_hacker Jul 24 '14 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. – j_random_hacker Jul 24 '14 at 12:35

2 Answers2

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).

U2EF1
  • 12,907
  • 3
  • 35
  • 37
  • 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 Jul 23 '14 at 21:20
  • 2
    @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? – Mark Ransom Jul 23 '14 at 21:24
  • 3
    @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. – StriplingWarrior Jul 23 '14 at 22:20
  • 1
    @MarkRansom X86, at least, has a swap (xchg) instruction. I am sure xor-swap is a useful optimization on some (register starved?) chips. – U2EF1 Jul 23 '14 at 22:30
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.

Mike Vokits
  • 21
  • 3