連続整数列の排他的論理和（xor）

連続する非負整数の排他的論理和（xor）を高速に計算する方法について。

次の関数 \(f: \mathbb{N}_0 \rightarrow \mathbb{N}_0 \) を考える。

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

ただし、 \(\oplus\) はビットごとの排他的論理和（xor）である。素直に計算するなら \(O(n)\) の計算量が必要だが、実はこの関数は排他的論理和を一回も取らずに結果を得ることができる。

性質 #

任意の非負整数 \(m\) に対し、

\begin{align} 2m \oplus (2m+1) = 1. \end{align}

この性質から、任意の非負整数 \(m\) に対し、

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

が成り立つ。すなわち、\(f\) は4要素ごとにゼロになることがわかる。よって、\(f\) は、

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

と \(O(1)\) で計算できる。

これを用いれば、任意の連続自然数の和 \begin{align} g(n, m) := n \oplus (n+1) \oplus \dots \oplus m\ \ (0 < n < m) \end{align}

は

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

と \(O(1)\) と計算できる。