\(f(i) = 1 \oplus 2 \oplus\cdots\oplus i\) とすると、\begin{eqnarray}
f(i)
=
\begin{cases}
0 & ( i = 4k) \\
4k+1 & ( i = 4k+1) \\
3 & ( i = 4k+2) \\
4k & ( i = 4k+3) \\
\end{cases}
\end{eqnarray}
となる(ARC133D)。\(4k+2\) の形は現れない。

多項式として見る

\(\mathbb{F}_2[x]\) と解釈するとよい場合がある。例えば、xor と shift でできる集合は gcd の倍数である(AEC084F)。

Trie木において、+1は最右パスの子のswapに対応する(AGC057C)。