# Compute Exclusive OR(xor) of Consecutive Integers

This page shows how to calculate xor of nonnegative consecutive integers in constant time.

Consider the following function $$f:\mathbb{N}_{0}\rightarrow\mathbb{N}_{0}$$:

\begin{align}
f(n) = 1 \oplus 2 \oplus \dots \oplus n
\end{align}

where $$\oplus$$ is bitwise exclusive OR(xor) operator. One can compute the result of the function without applying xor $$n – 1$$ times.

#### Theorem

\begin{align}
2m \oplus (2m + 1) = 1 \ \ \forall m \in \mathbb{N}_{0}
\end{align}

By this fact,

\begin{align}
4m \oplus (4m+1) \oplus (4m+2) \oplus (4m+3) = 0
\end{align}

follows for all $$m \in \mathbb{N}_{0}$$. In other words, $$f$$ is equal to $$0$$ for every 4 elements. Thus, one can calculate $$f$$ in $$O(1)$$ by

\begin{align}
f(n) = \begin{cases}
n, & n \equiv 0 \pmod 4 \\
1, & n \equiv 1 \pmod 4 \\
n + 1, & n \equiv 2 \pmod 4 \\
0. & n \equiv 3 \pmod 4
\end{cases}
\end{align}

In addition, xor of the consecutive integers

\begin{align}
g(n, m) := n \oplus (n+1) \oplus \dots \oplus m\ \ (0 < n < m)
\end{align}

can be calculated in $$O(1)$$ by

\begin{align}
g(n, m) = f(n-1) \oplus f(m).
\end{align}