本文整理自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)$ 算法