本文整理自flyinghearts的博客。

记 $f(x,y)$ 为从 $x$ 一路异或到 $y$ 的值。$\mathrm{xor}$ 异或，$\mathrm{or}$ 是或。

对于 $f(2^k,2^{k+1}-1)$ 这 $2^k$ 个数，它们的最高位显然是第 $k$ 位。最高位的 $1$ 的个数为 $2^k$。

$k \geq 1$ 时， $2^k$ 为偶数，$\mathrm{xor}$ 下来成了 $0$。将这些数的最高位抹去，$f$ 的值不变，则 $f(2^k,2^{k+1}-1)=f(2^k-2^k,2^{k+1}-1-2^k)=f(0,2^k-1)$。

则 $f(0,2^{k+1}-1) = f(0,2^k-1)\ \mathrm{xor}\ f(2^k,2^{k+1}-1)=0$ 当 $k \geq 1$ 时。

即 $f(0,2^k-1)=0$ 当 $k \geq 2$ 时。

对于 $n \geq 4$，设其最高位 $1$ 在第 $k$ 位，则 $k \geq 2$。

$f(0,n)=f(0,2^k-1)\ \mathrm{xor}\ f(2^k,n)=f(2^k,n)$

对于 $2^k \sim n$ 这 $n-2^k+1$ 个数，最高位有 $m=n-2^k+1$ 个 $1$。

$n$ 与 $n-2^k$ 同奇偶。

• 当 $n$ 为奇数时

$m$ 是偶数，则 $f(2^k,n)=f(0,n-2^k)$。

递降这个公式，也即相当于不断剥去 $n$ 最高位的 $1$，得到 $f(0,n)=f(0,n \bmod 4)$。

$n \equiv 1 \pmod 4$ 时，$f(1,n)=f(0,n)=f(0,1)=1$。

$n \equiv 3 \pmod 4$ 时，$f(1,n)=f(0,n)=f(0,3)=0$。

• 当 $n$ 为偶数时

$m$ 是奇数，则 $f(2^k)=f(n-2^k)\ \mathrm{or}\ 2^k$。

递降这个公式，得 $f(0,n)=\eta\ \mathrm{or}\ f(0,n \bmod 4)$。

其中 $\eta$ 是 $n$ 将第 $0,1$ 位置 $0$ 后的数。

$n \equiv 0 \pmod 4$ 时，$f(1,n)=f(0,n)=n$。

$n \equiv 2 \pmod 4$ 时，$f(1,n)=f(0,n)=n+1$。

综上所述 $$ f(1,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} $$

因此我们得到了 $\mathrm{O}(1)$ 算法