Calculating XOR from 1 to n: Why does this method work?

Question

Given a number n, the task is to find the XOR from 1 to n. Why does the following algorithm work?

1. Find the remainder of n by moduling it with 4.
2. If rem = 0, then XOR will be same as n.
3. If rem = 1, then XOR will be 1.
4. If rem = 2, then XOR will be n+1.
5. If rem = 3 ,then XOR will be 0.

Answer 1

Here are two different ways to see this, first a more "direct reasoning" way and second by induction. Let $\oplus$ denote the XOR operation.

Direct reasoning:

If $x$ is an even number, then what is $x \oplus (x + 1)$? Notice that because $x$ is even (ends in a $0$), $x + 1$ only modifies the last bit, so that all the other bits will be the same as $x$, and so they cancel out. Therefore, $x \oplus (x + 1) = 1$.

From this, we can "pair up" all the numbers in the whole compuation $1 \oplus 2 \oplus 3 \oplus ... \oplus n$: \begin{align*} 0 \oplus 1 = 1 \\ 2 \oplus 3 = 1 \\ 4 \oplus 5 = 1 \\ \cdots \end{align*} Here we have $\lfloor \frac{n+1}{2} \rfloor$ pairs which XOR out to $1$, and then possibly one lone $n$ left at the end. The result follows from this computation. For example, if $n$ is a multiple of $4$, there will be one number left at the end ($n$), and otherwise an even number of pairs with xor $1$, so all of those xor out to $0$, and we are left with $n$. If $n$ has remainder $3$ mod $4$, the pairing is exact and there are an even number of pairs, so the answer is $0$.

Induction:

We can also see this by an induction argument. In the base case, $n = 0$, there are no numbers to xor so the xor is $0$. Or you can do $n = 1$ as a base case, to get xor $1$.

For the induction step, it depends on the case. For example: going from remainder 0 to remainder 1, we know that the previous answer was $(n-1)$, so now the answer is $(n-1) \oplus n = 1$ because $n-1$ only differs in the last bit. Going from remainder $1$ to remainder $2$, we know that the previous answer was $1$, and now we xor with $n$ so we will get $n \oplus 1$, which is the same as $n + 1$ since $n$ is even. The other cases are similar.

Answer 2

The process can be summarized by the four rules below (the right operand is the bitwise XOR up to the left operand minus one):

$$\begin{align} (4n+0)&\oplus0=4n\\ (4n+1)&\oplus4n=1\\ (4n+2)&\oplus1=4n+3\\ (4n+3)&\oplus(4n+3)=0\end{align}$$

E.g.

$$\begin{align} 101101|00&\oplus000000|00=101101|00\\ 101101|01&\oplus101101|00=000000|01\\ 101101|10&\oplus000000|01=101101|11\\ 101101|11&\oplus101101|11=000000|00\end{align}$$

Answer 3

Add 0 to the xor sum, which doesn't change it.

Then split the sum into groups of four from 4k to 4k+3, which will always have an xor of 0.

Depending on n modulo 4, these groups cover everything, or there is n = 4k left, or n, n+1 = 4k, 4k+1 left, or n, n+1, n+2 = 4k, 4k+1 and 4k+2 left. Calculate the xor of these 1, 2, or 3 numbers, and you have the result.