Finding XOR of all even numbers from n to m Problem : Given a range $[n,m]$, find the xor of all even numbers in this range. Constraints : $1 \le n \le m \le 10^{18}$
How do we solve this problem?
P.S. I asked this question at stackoverflow but that was not the appropriate place to ask this question. So I re-asked it here.
 A: Let $$f(n) = \oplus_{\text{$i$ even}}^n i$$
and wlog $n$ is even (replace it with $n-1$ if it's odd, without any change to the answer).
Then


*

*if $n \equiv 0 \pmod{8}$, have $f(n) = n$; 

*if $n \equiv 2 \pmod{8}$, have $f(n) = 2$;

*if $n \equiv 4 \pmod{8}$, have $f(n) = n+2$;

*if $n \equiv 6 \pmod{8}$, have $f(n) = 0$.


These are easily proved by considering the binary expansion of $f(n)$: in all cases, we want $f(n-2) \oplus n$.


*

*If $n \equiv 2 \pmod{8}$, then we are taking the previous sum and XORing it with $n$; that is $(n-2) \oplus n$ inductively, which is $2$.

*If $n \equiv 4 \pmod{8}$, then we are taking the previous sum and XORing it with $n$; that is $2 \oplus n$, which (since $n$ ends with two zeros in its expansion) is $n+2$.

*If $n \equiv 6 \pmod{8}$, then likewise it is $n \oplus n = 0$.

*If $n \equiv 0 \pmod{8}$, then it is $0 \oplus n = n$.


Base case is easy.
Then the xor in range $[n, m]$ is $f(m) \oplus f(n-1)$.
A: If n is odd, change n to n-1.
Starting with n, find the next number by adding 2 to the previous number.
f(n) = $2 \oplus 4 \oplus ... \oplus (n-2) \oplus n$
Converting the numbers to binary, its easy to see that the least significant bit of all the numbers is same (because all are even numbers). Adding 2 to previous number, say x, to get (x+2) its equivalent to ((x/2) + 1)*2. 
Converting the numbers in binary and using the above observation we can easily infer the following:
f(n) = 2*g(n), where g(n) = $1 \oplus 2 \oplus ... \oplus (n-2)/2 \oplus (n/2)$
So it reduces the problem to find the XOR of all numbers from 1 to k where k = n/2. This can be solved as follows:
Then


*

*if $k \equiv 0 \pmod{4}$, have $f(n) = k$; 

*if $k \equiv 1 \pmod{4}$, have $f(n) = 1$;

*if $k \equiv 2 \pmod{4}$, have $f(n) = k+1$;

*if $k \equiv 3 \pmod{4}$, have $f(n) = 0$.


This can be observed from the pattern:
0000 <- 0  [k]
0001 <- 1  [1]
0010 <- 3  [k+1]
0011 <- 0  [0]
0100 <- 4  [a]
0101 <- 1  [1]
0110 <- 7  [k+1]
0111 <- 0  [0]
1000 <- 8  [k]
1001 <- 1  [1]
1010 <- 11 [k+1]
1011 <- 0  [0]
1100 <- 12 [k]
1101 <- 1  [1]
1110 <- 15 [k+1]
1111 <- 0  [0]

So for the range [n,m] the ans is $f(m) \oplus f(n-1)$
P.S. This is how I solved it and got it right.
A: Something like this:
For bit $k$,
where $k=0$ is the 
units bit,
blocks of length
$2^{k+1}$
xor to zero,
since there are
$2^k$ with a $0$
and
$2^k$ with a $1$.
Therefore,
we can xor the $k$-th bit
from
$i=
n+\lfloor \frac{m-n}{2^{k+1}} \rfloor
$
to
$m$
to get that bit,
since the blocks of
length $2^{k+1}$
xor to zero.
Do this until
$2^{k} > m$.
