5 ms·
(n+1)%2 = if (n+1) is divisible by 2 then 0 else 1 = (n+1) & 1 = ~(n & 1) ((n + (n % 2)) // 2) % 2 = ((n + (n & 1)) >> 1) & 1 = ((n & 2) >> 1) ^ (n & 1) = (n ^
by smlckz 6y ago
(n+1)%2 = if (n+1) is divisible by 2 then 0 else 1 = (n+1) & 1 = ~(n & 1)
((n + (n % 2)) // 2) % 2 = ((n + (n & 1)) >> 1) & 1 = ((n & 2) >> 1) ^ (n & 1) = (n ^ (n >> 1)) & 1
In human terms, that means XOR of 1, 2, ..., n is:
(if (n is divisible by 2) then n else 0) + (if ((if (n is divisible by 2) then n else n + 1) is divisible by 4) then 1 else 0)
Or, as code: n * ~(n & 1) + (n ^ (n >> 1)) & 1
Phew! Can this be made any simpler or smaller?
1 ^ 10 = 11, 11 ^ 11 = 0, 0 ^ 100 = 100, 100 ^ 101 = 001, 1 ^ 110 = 111, 111 ^ 111 = 0, 0 ^ 1000 = 1000, ...
----
If you have some time, take a pen and a paper and think it through, you'll really like it...
- Y_Y 6y agoThis is a really neat result. I bet Euler or Gauss already thought of it and the solution is somewhere in a book full of such solutions.
- kevinventullo 6y agoThe simplest formula from the OEIS page seems to be a(4n)=4n, a(4n+1)=1, a(4n+2)=4n+3, a(4n+3)=0. Once you have the formula in front of you, it’s easy to prove it by induction. A branchless implementation of this function with no multiplies or divides: f(x)=(x^(x&1-1))+(((x+1)&2)>>1)
- smlckz 6y agoCorrection: It is not ~(n & 1), but !(n & 1) Or ((~n) & 1) as ChrisLomont pointed out
- ChrisLomont 6y ago> n * ~(n & 1) This term results in huge numbers. Do you mean n * ((~n)&1)) ?
- smlckz 6y agoMy bad. Thanks for pointing it out.