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:
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:
After line 2:
= A0 + B0 - B0
= A0
After line 3:
= 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!
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.
ReplyDeleteIt is a clever trick, but not widely applicable.
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* ;-)
ReplyDeleteI agree it's not something you'd want to use - just an interesting confection!
Dalija.
ReplyDeleteJust updated post re your observation.
Well, you could just use XOR for any matching bit size pattern and not worry about the math overflows.
ReplyDeleteThat 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.
XORing - even cooler & even more obscure!
ReplyDeleteGoing to have to scribble that approach down to see it working!
I never considered the speed of the code being improved with a temp.
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. :)
ReplyDeleteXOR swap also has a problem if a and b use same storage location in which case result will be 0. XOR swap algorithm
ReplyDeleteSwap tricks have their place in assembly code when you need to achieve specific low level optimization.
ReplyDeleteGenerally in high level Delphi code I would consider such tricks harmful because you need to know and avoid the pitfalls.
Can of worms well and truly opened! 😜
ReplyDeleteCan of worms indeed 😉
ReplyDeleteIt 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...
ASM ☠️
ReplyDeleteDon't go there 😉
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