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

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.
• Do you mean the bitwise XOR ? Feb 6 at 7:55
• Are you asking about 1 XOR 2 XOR ... XOR n-1 XOR n? Feb 6 at 19:39
• Yes i mean that @SolomonUcko Feb 7 at 10:33

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.

• Good explanation. It is implicit in the answer, particularly the first part, and perhaps it is also implicit in the question, that $\oplus$ is an associative operator, so we are allowed to evaluate e.g. $((a\oplus b)\oplus c)\oplus d$ as $(a\oplus b)\oplus(c\oplus d)$. Feb 9 at 7:10

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}

• @MonkaS: the rules are very easy to verify. Feb 7 at 10:36

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.