5 ms·
That XOR Trick
- mytailorisrich 4y ago> 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'.
- sischoel 4y agoWhy is that though? Wouldn't something like `mov eax 0` also work?
- gruturo 4y agoAbsolutely (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.
- anitil 4y agoIt begs a question though: How many instructions in <insert ISA here> are equivalent? I assume that a compiler writer has a list of equivalents and will typically choose the shorter one?
- icodestuff 4y agoThere are a number of considerations there. Size is only one of them. Speed and internal processor state effects are two others. For instance, a larger, slower instruction might prevent a pipeline stall in a particular function or might enable loop unrolling or might allow a shorter loop unrolling, while in a similar function that doesn’t pipeline the same way, the compiler will choose a faster instruction.
- anitil 4y agoYou're right I completely overlooked pipelining. I guess I'm out of my depth here
- IcePic 4y agoFor RISC ISAs like MIPS, then you can do a lot of ADD Reg0 to Reg0 and store result in Rx OR Reg0 with reg0 and store result in Rx XOR Reg0 with reg0 and .. The only issue is that for RISC, all these instructions are of equal length, so flipping them around would gain you very little, or more likely zero effect unless you are chasing some corner case thing like "XOR instruction value compresses slightly better than ADD because.."
- kevincox 4y agoWell that 0 that you are loading comes from the instruction, so it is already "there". It boils down to the fact that the instruction is sorter. In fact in theory the load is slower, because XOR has data dependencies on the arguments. So an out-of-order processor could be delayed. However x86 has special logic that XOR with itself doesn't carry any dependencies on the arguments.
- hansvm 4y agoIn addition to other concerns, processors usually treat xor specially since it was the best way to zero things for so long that it became ubiquitous. Often its performance impacts are equivalent to a noop.
- Demonsult 4y agoSee also, "Hacker's Delight" by Henry Warren for a deep dive into bit manipulation tricks.
- dsjoblom 4y agoThe “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.
- 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? :)
- Const-me 4y agoMy 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 ); }
- jmprspret 4y agoWent to bookmark this not realising I had already bookmarked it!
- lemoncucumber 4y agoIt took me a minute to figure out the last step of the final example since the author doesn’t quite spell it out. So for anyone else who’s feeling a little slow: Once you’ve partitioned the search space into “values where the ith bit is 0” and “values where the ith bit is 1” (for example, even and odd values if it happens to be the least significant bit), then you can simply iterate through all the input values and xor together all the values where the ith bit is 0, then xor those with all possible values where the ith bit is 0, and you’ve found one of the missing values. Repeat the process with 1 instead of 0 to find the other.
- Alham-Dulillah 4y agox ^= y ^ (y = x); //one-liner
- DylanSp 4y agoNitpick: I think the trick(s) also depend on XOR being associative. Are there any more complex applications of this, especially if you generalize it to any operator that obeys the necessary properties? I'm curious if there's any sort of interesting data structures you can build, probably building on commutative monoids where x `mappend` x == mempty for all x (the generalization of x^x == 0).