Went to bookmark this not realising I had already bookmarked it!
That XOR Trick
11–20 of 21 posts
Re: That XOR Trick
#12> 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?
In 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.
Re: That XOR Trick
#13Earlier quoted context omitted.
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.
It begs a question though: How many instructions in are equivalent? I assume that a compiler writer has a list of equivalents and will typically choose the shorter one?
Re: That XOR Trick
#14It 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.
Re: That XOR Trick
#15Earlier quoted context omitted.
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.
It begs a question though: How many instructions in are equivalent? I assume that a compiler writer has a list of equivalents and will typically choose the shorter one?
There 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.
Re: That XOR Trick
#16Earlier quoted context omitted.
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.
It begs a question though: How many instructions in are equivalent? I assume that a compiler writer has a list of equivalents and will typically choose the shorter one?
For 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.."
Re: That XOR Trick
#17Earlier quoted context omitted.
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.
Well 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.
Re: That XOR Trick
#18Earlier quoted context omitted.
It begs a question though: How many instructions in are equivalent? I assume that a compiler writer has a list of equivalents and will typically choose the shorter one?
There 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.
You're right I completely overlooked pipelining. I guess I'm out of my depth here
Re: That XOR Trick
#19Nitpick: 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).
Re: That XOR Trick
#20x ^= y ^ (y = x); //one-liner