> 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 gives ((n+1)%2)*n + (n+(n%2))//2 % 2
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 gives ((n+1)%2)*n + (n+(n%2))//2 % 2
((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...
I bet Euler or Gauss already thought of it and the solution is somewhere in a book full of such solutions.
a(4n)=4n,
a(4n+1)=1,
a(4n+2)=4n+3,
a(4n+3)=0.
f(x)=(x^(x&1-1))+(((x+1)&2)>>1)Or ((~n) & 1) as ChrisLomont pointed out
This term results in huge numbers. Do you mean n * ((~n)&1)) ?
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.
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
switch(n % 4) { case 0: return n; case 1: return 1; case 2: return n + 1; case 3: return 0; }