That XOR Trick
florian.github.io
That XOR Trick
1–10 of 21 posts
Re: That XOR Trick
#2> XOR on the same argument: x ^ x = 0
Those who have dabbled with x86 assembly will know that this is pretty much the standard to set a register to zero. Code is peppered with the likes of 'xor eax, eax'.
Re: That XOR Trick
#3See also, "Hacker's Delight" by Henry Warren for a deep dive into bit manipulation tricks.
Re: That XOR Trick
#4The “missing integer” example is awkward, because what’s interesting here is not whether you can solve the problem with xor or plus, but whether you need two loops or just one. Edit: I guess overflow is one consideration, as mentioned in the article.
Re: That XOR Trick
#5> 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.
Re: That XOR Trick
#6> 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 para…
>Warning: if x == y, then instead of swapping, the two values are set to zero.
Huh, what?
Re: That XOR Trick
#7> 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 para…
>Warning: if x == y, then instead of swapping, the two values are set to zero. Huh, what?
You'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;
}
x ^= x;
x ^= x;
x ^= x;
In contrast:
void regular_swap(int& x, int& y){
int tmp = x;
x = y;
y = tmp;
}
Re: That XOR Trick
#8> XOR on the same argument: x ^ x = 0 Those who have dabbled with x86 assembly will know that this is pretty much the standard to set a register to zero. Code is peppered with the likes of ' xor eax, eax '.
Why is that though? Wouldn't something like `mov eax 0` also work?
Re: That XOR Trick
#9> XOR on the same argument: x ^ x = 0 Those who have dabbled with x86 assembly will know that this is pretty much the standard to set a register to zero. Code is peppered with the likes of ' xor eax, eax '.
Why is that though? Wouldn't something like `mov eax 0` also work?
Absolutely (well, if you add the missing comma :) ), just less efficient.
That 0 has to come from somewhere, while in the other case XORing a register with itself does not involve loading any data. It's also shorter.
Re: That XOR Trick
#10My favorite application is comparing vectors. Example in C++:
// Compare 32 bytes for equality, with 2 AVX2 instructions
inline bool equals( __m256i a, __m256i b )
{
// When the vectors are equal, their XOR is completely zero..
__m256i xx = _mm256_xor_si256( a, b );
// ..and there's a special instruction to test the complete vector for zero
return (bool)_mm256_testz_si256( xx, xx );
}