3 ms·
You have to take overflow into account. In most cases, that would make the algorithm not very useful compared to just doing the swap with a third variable.
by Sacho 10y ago
You have to take overflow into account. In most cases, that would make the algorithm not very useful compared to just doing the swap with a third variable.
- JoeAltmaier 10y agoHm I don't think overflow will apply. Anything it does in an add will be undone by a subtract? Except that 2a, that might be trouble.
- mcintyre1994 10y agoImagine you only had 4 bit numbers (range 0-15) and you tried to do swap 14, 15 (1110, 1111). You can do that with xor but not with the add method, because you can't store a + b without a wider variable.
- jonsen 10y ago15 + 15 gives 14 14 - 15 gives 15
- mcintyre1994 10y agoThe way I wrote this was rubbish, edited. I was trying to get at if you have 1110, 1111 then 1110 + 1111 will overflow, but you could xor them.
- jonsen 10y ago1110 + 1111 = 1101 1101 - 1110 = 1111 1101 - 1111 = 1110 Overflow doesn't matter if you just want to swap.
- Sacho 10y ago(Assuming two's complement arithmetic, as amelius pointed out - I don't know if all programming languages and platforms use it)
- mcintyre1994 10y agoThat's a really smart observation I hadn't made, thanks for explaining!
- amelius 10y agoIn two's complement arithmetic, you are basically computing modulo N (N = 2 to the power of the number of bits). So overflow will not interfere with the swap operation.