3 ms·
> Application 1: In-Place Swapping Warning: if x == y, then instead of swapping, the two values are set to zero. So this swapping trick works only for x!=y.
by dragontamer 4y ago
> Application 1: In-Place Swapping
Warning: if x == y, then instead of swapping, the two values are set to zero.
So this swapping trick works only for x!=y.
---------
The other tricks are interesting, and likely hold the key to some kind of parallel programming trick, as a sequence of XORs is trivially parallelizable through the prefix-sum pattern.
All of the other tricks are O(n) number of XOR operations, while parallel prefix-sum is O(log(n)) depth and O(n) total work.
- garaetjjte 4y ago>Warning: if x == y, then instead of swapping, the two values are set to zero. Huh, what?
- dragontamer 4y agoYou're right. Sorry, my bad. I misremembered the actual issue. The issue is: void xor_swap(int& x, int& y){ x ^= y; y ^= x; x ^= y; } The issue is *aliasing*. If the pointer &x == &y, then everything goes to crap. When the pointers alias to themselves, the function degenerates into: x ^= x; x ^= x; x ^= x; Which sets x (and the y value) to zero. In contrast: void regular_swap(int& x, int& y){ int tmp = x; x = y; y = tmp; } This always works, even with aliasing.
- Alham-Dulillah 4y agoThis one-liner works for x==y: x ^= y ^ (y = x); Is this really code, or some kind of new text emojis? :)