Skip to main content

Compute Exclusive OR(xor) of Consecutive Integers

·187 words·
Mathematics Algorithm
Table of Contents

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.


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


Throw away pack expansion results in C++
·524 words
Techniques C++
Handle permutations with duplicates at compile time
·594 words
Techniques C++
`Constraints` improves readability of SFINAE code
·322 words
Techniques C++ SFINAE