6 ms·
> XOR all values between 1 and n An O(n) algorithm!? You'd expect there to be a closed-form solution for this, analogous to summing a series using n*(n-1)/2.
by tlb 6y ago
> XOR all values between 1 and n
An O(n) algorithm!? You'd expect there to be a closed-form solution for this, analogous to summing a series using n*(n-1)/2.
OEIS to the rescue. http://oeis.org/A077140 http://oeis.org/A077140 gives ((n+1)%2)*n + (n+(n%2))//2 % 2
- lifthrasiir 6y agoIt was not super obvious to me, but the actual sequence is https://oeis.org/A003815 https://oeis.org/A003815 which is the absolute value of A077140. The entry for the latter gives another formula for A003815 however, which is distinct from a formula (1+3x-x^2+x^3)*x/(1-x^4)/(1-x^2) given in A003815.
- 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.
- LVB 6y agoWondering at what value of n the closed form solution uses fewer cycles than n xors, since that’ll end being the follow-up question :)
- johnfn 6y agoErr... if you sum all the numbers that’s O(n) as well.
- abalaji 6y agoright but OP’s solution for this part of the problem is assumed to be instantaneous (ie O(0))
- smlckz 6y agoWhat is O(0)? Computation that takes 0 time? Does that make any sense?
- tantalor 6y agoNo-op :)
- randomswede 6y agoIt is the class of functions that have the constant value 0, with a canonical exemplar f(n) = 0 (and despite having tried, I cannot find any other function, up to choice of variable name). In terms of algorithms, I suspect that no actual algorithm fits into it and as such it is more a curiosity than actually useful. However, O(0) is not the same as O(1), as we cannot find a constant c such that 0c dominates all possible functions that 1c can dominate.
- shiftingleft 6y agoYou probably mean O(1). Although: that's not true for arbitrarily sized integers either. Multiplication in O(1) implies P = NP (which further implies NP = PSPACE): https://cs.stackexchange.com/a/1661/129151 https://cs.stackexchange.com/a/1661/129151
- abalaji 6y agoYeah I meant O(1), whoops
- deleted 6y ago
- PufPufPuf 6y ago...or simply switch(n % 4) { case 0: return n; case 1: return 1; case 2: return n + 1; case 3: return 0; }