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

3 Answers 3


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$.


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.

  • 1
    $\begingroup$ 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)$. $\endgroup$ 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}$$


$$\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}$$

  • $\begingroup$ @MonkaS: the rules are very easy to verify. $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.