Swap two integers without using a temporary variable

Here's a clever little algorithm you can use to swap two integers without using a temporary variable.

I rediscovered this tip, by Muhammad Saied, while reviewing my Delphi Tips micro-site.

Dunno why, but I find this strangley pleasing!

Assume we have two integers, A & B, both of which have values assigned. Swap their values like this:

    A := A + B;
    B := A - B;
    A := A - B;

To follow this through, let:

  • A0 and B0 be the original values of A and B respectively
  • A1 be the value of A after line 1
  • B2 be the value of B after line 2
  • A3 be the value of A after line 3

We have:

After line 1:

    A1 = A0 + B0

After line 2:

    B2 = A1 - B0
       = A0 + B0 - B0
       = A0

After line 3:

    A3 = A1 - B2
       = A0 + B0 - B2
       = A0 + B0 - A0
       = B0

Et voilà. Very cunning Muhammad!

EDIT: As Dalija Prasnikar pointed out in the comments, because you're adding values, there's a danger of overflow errors.

So what d'you reckon? Would you use that trick?

For me, the answer is a resounding "no way". It's clever & it intrigues me, but it's not exactly self documenting in the way swapping two integers via a temporary variable is, now is it? And the likelihood of getting that code wrong is high too.

These days, I think we can spare a few bytes for that temp variable!

Comments

It is important to note that, depending on the values of a and b, arithmetic swapping can cause overflow or underflow and will fail in such cases.

It is a clever trick, but not widely applicable.

Delphidabbler said…
That's a good point: so to use it safely you'd need to cast up to a wider integer, do the swap and cast back! Bang goes the ”no temp variables” *advantage* ;-)

I agree it's not something you'd want to use - just an interesting confection!
Delphidabbler said…
Dalija.

Just updated post re your observation.
C Johnson said…
Well, you could just use XOR for any matching bit size pattern and not worry about the math overflows.

That said, flipping through a temp variable is more likely to end up in a register and run a heck of a lot faster than all this data shuffling and logic.
Delphidabbler said…
XORing - even cooler & even more obscure!

Going to have to scribble that approach down to see it working!

I never considered the speed of the code being improved with a temp.
Eric said…
It's like a small Rube Goldberg machine : does the trick but in a convoluted, unsafe and inefficient fashion, just for the fun of dancing around the obvious. :)
XOR swap also has a problem if a and b use same storage location in which case result will be 0. XOR swap algorithm
Swap tricks have their place in assembly code when you need to achieve specific low level optimization.

Generally in high level Delphi code I would consider such tricks harmful because you need to know and avoid the pitfalls.
Delphidabbler said…
Can of worms well and truly opened! 😜
Can of worms indeed 😉

It is still nice to know about such tricks, even though chances they will be useful are rather slim. Though, Delphi supports writing assembly code so you never know...
Delphidabbler said…
ASM ☠️
Don't go there 😉
Stefan Glienke said…
In the age of superscalar CPUs that execute multiple instructions at the same time this algo is absolutely worthless. Performing these operations is way slower than doing a one temp var swap. Fun fact: in many situations a two temp var swap can be even faster because the two reads execute at the same time as well as the two writes while the one var swap has a data dependency that needs all three assignments to be executed sequentially.

Popular posts from this blog

New Unit2NS Application Released in Beta

Embarcadero Announce RAD Studio 11 Is Coming

Some Features of the Upcoming Delphi 11 (probably)