Apart from these applications of XOR, a favourite one is using Bitwise AND to find Even/Odd numbers.
That XOR Trick (2020)
31–40 of 141 posts
Re: That XOR Trick (2020)
#32Earlier quoted context omitted.
No, again, that's not my point. The code from the article is O(2n) when it could be O(n). I know we're not supposed to care about constant factors, but I've lived in a world where not micro optimizing the ever loving shit out of my software could potentially make people throw up, so this sort of stuff kind of stands out to me.
The code in the article is written in Python, whose only for loop is for-each. It is 2N XOR operations, regardless of whether you use one or two loops. I probably would have written it with a single loop, using the `enumerate` iterator adapter. But in Python, two loops is almost certainly more efficient.
You can loop over the range and then do result ^= i ^ A[i]. If adapters are slow you don't need them here.
Having only one loop gives you a better memory access pattern, because it's 2 XOR operations in between each memory access. Two loops is the same number of instructions, but it spends one loop ignoring memory and then another loop doing rapid-fire memory accesses. In python there's enough overhead that it's unlikely to matter. But in a faster language running on a busy machine that could make a real difference.
Re: That XOR Trick (2020)
#33Earlier quoted context omitted.
Its main benefit is to avoid having extra data structure (like hash map) to find the missing or duplicate, using O(n) time and O(1) space.
No, again, that's not my point. The code from the article is O(2n) when it could be O(n). I know we're not supposed to care about constant factors, but I've lived in a world where not micro optimizing the ever loving shit out of my software could potentially make people throw up, so this sort of stuff kind of stands out to me.
O(2n) doesn't exist. The whole point of big O is that you ignore such "trivial" things as what factor comes before the n
Re: That XOR Trick (2020)
#34The partitioning algorithm to find two missing/duplicate numbers is clever, I wouldn't have thought of that. It should also work if you have a list with 1 missing and 1 duplicate, yeah? You'd probably have to do an extra step to actually find out which number is missing and which is a duplicate after you find the two numbers.
> If more than two elements are missing (or duplicated), then analyzing the individual bits fails because there are several combinations possible for both 0 and 1 as results. The problem then seems to require more complex solutions, which are not based on XOR anymore.
If you consider XOR to be a little bit more general, I think you can still use something like the partitioning algorithm. That is to say, considering XOR on a bit level behaves like XOR_bit(a,b)=a+b%2, you might consider a generalized XOR_bit(a,b,k)=a+b%k. With this I think you can decide partitions with up to k missing numbers, but I'm too tired to verify/implement this right now.
Re: That XOR Trick (2020)
#35Earlier quoted context omitted.
No, again, that's not my point. The code from the article is O(2n) when it could be O(n). I know we're not supposed to care about constant factors, but I've lived in a world where not micro optimizing the ever loving shit out of my software could potentially make people throw up, so this sort of stuff kind of stands out to me.
O(2n) doesn't exist. The whole point of big O is that you ignore such "trivial" things as what factor comes before the n
Did I not say that?
Re: That XOR Trick (2020)
#36Earlier quoted context omitted.
It really tickles my brain in a lovely way that it avoids all overflow risk as well
There is no overflow risk. The trick works on any Abelian group. N-bit values form an Albanian group with xor where 0 is the identity and every element is its own inverse. But N-bit values also form an Abelian group under addition with overflow, where 0 is the identity and 2s-compliment is the inverse. If you’re working on an architecture where a single multiplication and a bit shift is cheaper than N xor’s, and wher…
[deleted]
Re: That XOR Trick (2020)
#37Fun fact: the xor swap fails when the variables are aliases. This was the trick used in one of the underhanded code competitions.
Basically xor swapping a[i] with a[j] triggered the evil logic when i was equal to j.
Re: That XOR Trick (2020)
#38In ye olden days, bit manip operations were faster than algebraic operations. And sometimes even faster than a load immediate, hence XOR AX, AX instead of MOV AX, 0.
"xor ax, ax" is still in use today. The main advantage is that it is shorter, just 2 bytes instead of 3 for the immediate, the difference is bigger in 32 and 64 bit mode as you have to have all these zeroes in the instruction. Shorter usually mean faster, even if the instruction itself isn't faster.
In long mode, compilers will typically emit `xor eax, eax`, as it only needs 2 bytes: The opcode and modrm byte. `xor ax, ax` takes 3 bytes due to the operand size override prefix (0x66), and `xor rax, rax` takes 3 bytes due to the REX.W prefix. `xor eax, eax` will still clear the full 64-bit register.
Shorter basically means you can fit more in instruction cache, which should in theory improve performance marginally.
Re: That XOR Trick (2020)
#39Fun fact: you can show that there is another binary operator that performs the same triple assignment swap.
Re: That XOR Trick (2020)
#40I like the 'store prev ^ next' trick for lists that can be walked from the front or from the back.