Very well written article! I used xor just as fast clear register :)
That XOR Trick (2020)
81–90 of 141 posts
Re: That XOR Trick (2020)
#82I figured out the solution of using addition directly.
A caveat with addition is that addition can grow the number of significant bits needed, and thus overflow (for large-enough values of n).
One aspect of XOR is that it is the same as binary addition without carry, and therefore it does not overflow.
Re: That XOR Trick (2020)
#83Fun 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.
It would set a[i] to zero instead of swapping two values, right?
Yes. Now we only need a legit use case for code that swaps values only if they are in different locations, otherwise zeroes the aliased location. Then we can finally do it using the xor swap!
Re: That XOR Trick (2020)
#84Earlier quoted context omitted.
> The trick works on any Abelian group ( https://en.wikipedia.org/wiki/Abelian_group -- I'll use ⋆ as the Abelian group's operation, and ~ for inversion, below.) I believe you are implying: (g(1) ⋆ ... ⋆ g(n)) ⋆ ~(g(i(1)) ⋆ g(i(2)) ⋆ ... ⋆ g(i(n-1))) = g(m) where "m" is the group element index that is not covered by "i". However, for this to work, it is requried that you can distribute the inversion ~ over the group…
> ... Does distributivity of inversion ~ over operation ⋆ follow from the other Abelian group axioms / properties? If so, how? It does. For all x and y: (1) ~x ⋆ x = 0 (definition of the inverse) (2) ~y ⋆ y = 0 (definition of the inverse) (3) (~x ⋆ x) ⋆ (~y ⋆ y) = 0 ⋆ 0 = 0 (from (1) and (2)) (4) (~x ⋆ ~y) ⋆ (x ⋆ y) = 0 (via associativity and commutativity) In (4) we see that (~x ⋆ ~y) is the inverse of (x ⋆ y). That…
Awesome, thanks! :)
Re: That XOR Trick (2020)
#85For calculating the XOR of 1 to n there is a closed form solution, so no need to XOR them together in a loop. (n & ((n & 1) - 1)) + ((n ^ (n >> 1)) & 1) Or a much more readable version [ n, 1, n + 1, 0 ][n % 4] which makes it clear that this function cycles through a pattern of length four. Why this works can be seen if we start with some n that is divisible by four, i.e. it has the two least significant bits clear,…
Fascinating. It can see it work but I still can't really wrap my head around where the magic cycle length of 4 comes from.
[deleted]
Re: That XOR Trick (2020)
#86For calculating the XOR of 1 to n there is a closed form solution, so no need to XOR them together in a loop. (n & ((n & 1) - 1)) + ((n ^ (n >> 1)) & 1) Or a much more readable version [ n, 1, n + 1, 0 ][n % 4] which makes it clear that this function cycles through a pattern of length four. Why this works can be seen if we start with some n that is divisible by four, i.e. it has the two least significant bits clear,…
Fascinating. It can see it work but I still can't really wrap my head around where the magic cycle length of 4 comes from.
There are essentially two bits of information in the 'state' of this iterated algorithm:
a) Are all the non-lowest bits zero, or are they the value of the latest N
b) the value of the lowest bit
So the cycle of (N, 1, N+3, 0) corresponds to (A) and (B) being: (0,0), (0,1), (1,1), (1, 0) - i.e. the 4 possible combinations of these states.
Re: That XOR Trick (2020)
#87For calculating the XOR of 1 to n there is a closed form solution, so no need to XOR them together in a loop. (n & ((n & 1) - 1)) + ((n ^ (n >> 1)) & 1) Or a much more readable version [ n, 1, n + 1, 0 ][n % 4] which makes it clear that this function cycles through a pattern of length four. Why this works can be seen if we start with some n that is divisible by four, i.e. it has the two least significant bits clear,…
In your array-based equation, you say n+1, but in your explanation you say n+3. Is that a mistake?
No, that is correct, those two n represent slightly different things. n + 3 is the value after n XOR n + 1 XOR n + 2, so the n in the array index expression is n + 2 from the explaination and n + 3 results from (n + 2) + 1. I thought about how I could make this less confusing but it just became more confusing in my mind, so just used n in both cases.
Re: That XOR Trick (2020)
#88For calculating the XOR of 1 to n there is a closed form solution, so no need to XOR them together in a loop. (n & ((n & 1) - 1)) + ((n ^ (n >> 1)) & 1) Or a much more readable version [ n, 1, n + 1, 0 ][n % 4] which makes it clear that this function cycles through a pattern of length four. Why this works can be seen if we start with some n that is divisible by four, i.e. it has the two least significant bits clear,…
In your array-based equation, you say n+1, but in your explanation you say n+3. Is that a mistake?
There's a bit of a trick in that solution: n is assumed to have the lower two bits clear so for an arbitrary n the array would really be:
[(n & ~3), 1, (n & ~3) + 3, 0][n % 4]
where the (n & ~3) makes sure those lower 2 bits are cleared. But note that we only ever can look at the first element when n % 4 == 0. In that case, (n & ~3) == n already. And further, we only ever can look at the third element when n % 4 == 2. In that case (n & ~3) == n - 2, so (n & ~3) + 3 == n + 1. Hence the array can be simplified to the one given in the other comment.
Re: That XOR Trick (2020)
#89For calculating the XOR of 1 to n there is a closed form solution, so no need to XOR them together in a loop. (n & ((n & 1) - 1)) + ((n ^ (n >> 1)) & 1) Or a much more readable version [ n, 1, n + 1, 0 ][n % 4] which makes it clear that this function cycles through a pattern of length four. Why this works can be seen if we start with some n that is divisible by four, i.e. it has the two least significant bits clear,…
Fascinating. It can see it work but I still can't really wrap my head around where the magic cycle length of 4 comes from.
If we generalize the problem to base k (they are k-1 duplicate of each number except the missing number, find missing one using base k-wise addition) then we can see the cycle is the smallest number such the base k-wise addition from 1 to the number is zero and it is power of k will form a cycle. I'm not sure if all such numbers are power of k if they exists or if there is an upper bound on them. For example in base 4 there appears to be no such cycle.
Re: That XOR Trick (2020)
#90I figured out the solution of using addition directly. A caveat with addition is that addition can grow the number of significant bits needed, and thus overflow (for large-enough values of n). One aspect of XOR is that it is the same as binary addition without carry , and therefore it does not overflow.
Use unsigned (modulo) and overflow doesn't affect the result.