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

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

• Find the remainder of n by moduling it with 4.

• If rem = 0, then XOR will be same as n.

• If rem = 1, then XOR will be 1.

• If rem = 2, then XOR will be n+1.

• If rem = 3, then XOR will be 0.

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.

StackExchange Computer Science Q#157353, answer score: 19