4 ms·
I have an alternative to the xor trick that doesn't suffer from zeros. def swap(a,b): a=a-b b=a+b a=b-a return a,b
by PartiallyTyped 6y ago
I have an alternative to the xor trick that doesn't suffer from zeros.
def swap(a,b):
a=a-b
b=a+b
a=b-a
return a,b
- mrmuagi 6y agoHmm, swaps the zero problem for a overflow/underflow one?
- contravariant 6y agoIf you stick to multiplication and addition then the beauty of modular arithmetic ensures that over and underflow are only a problem if your final result under/overflows. In particular you can solve the problem in this article by just subtracting the numbers from 1+2+...+n-1+n. The remainder will be your missing number (though be careful with the 1+2+...+n-1+n = n(n-1)/2 formula; division by 2 is very much not compatible with arithmetic modulo a power of 2, so divide first then multiply, or keep a running total if you want to be flexible).
- ganafagol 6y agoWorse. The zero problem does not exist if the two variables are at different memory locations. The overflow problem of this solution always exists. Plus, if a and b are at the same memory location, it suffers from the same zero problem.
- simias 6y agoThat suffers from the same problem if a and b are pointers to the same thing (which was the issue in my code, since I indexed the same cell of the array). Note that the problem is not that a and b have the same value, or even that one of them is 0, it's that a and b alias to the same memory location, effectively being two handles to the same variable.
- Izkata 6y agoUh, def swap(a, b): return b, a ? Or since this is presumably python, just inline it without a function: (a, b) = (b, a)