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

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

    ReplyDelete
  2. 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!

    ReplyDelete
  3. Dalija.

    Just updated post re your observation.

    ReplyDelete
  4. C Johnson7:22 pm

    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.

    ReplyDelete
  5. 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.

    ReplyDelete
  6. 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. :)

    ReplyDelete
  7. XOR swap also has a problem if a and b use same storage location in which case result will be 0. XOR swap algorithm

    ReplyDelete
  8. 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.

    ReplyDelete
  9. Can of worms well and truly opened! 😜

    ReplyDelete
  10. 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...

    ReplyDelete
  11. ASM ☠️
    Don't go there 😉

    ReplyDelete
  12. 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.

    ReplyDelete

Post a Comment

Comments are very welcome, but please don't comment here if:

1) You have a query about, or a bug report for, one of my programs or libraries. Most of my posts contain a link to the relevant repository where there will be an issue tracker you can use.

2) You have a query about any 3rd party programs I feature, please address them to the program's developer(s) - there will be a link in the post.

3) You're one of the tiny, tiny minority who are aggressive or abusive - in the bin you go!

Thanks

Popular posts from this blog

New String Property Editor Planned For RAD Studio 12 Yukon 🤞

Multi-line String Literals Planned For Delphi 12 Yukon🤞

Call JavaScript in a TWebBrowser and get a result back