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}