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}