ビットごとの排他的論理和の性質

数は非負整数として，ビットごとの排他的論理和を排他的ビット和と呼び， $\oplus$ で表す（または ^）．

・ $x \oplus x = 0$ ,　 $x \oplus 0 = x$

　　👉　swap(x, y): x ^= y, y ^= x, x ^= y

・ $x + y = ((x \wedge y) \ll 1) + (x \oplus y)$

　　👉　 $x + y \ge x \oplus y$ 　（ $\because 0 \le (x \wedge y) \ll 1$ ）

　　👉　 $x + y = x \oplus y \Leftrightarrow x \wedge y = 0$

・ ${ \begin{eqnarray} \bigoplus_{x = 1}^{n} x = \left\{ \begin{array}{ll} n & (n \equiv 0 \bmod 4) \\ 1 & (n \equiv 1 \bmod 4) \\ n \oplus 1 & (n \equiv 2 \bmod 4) \\ 0 & (n \equiv 3 \bmod 4) \end{array}\right. \end{eqnarray}}$

　　👉　 $n = 2^k \,(2 \le k)$ のとき， $\bigoplus_{x = 1}^{n} x = n$

リンク集（未読含む）

競技プログラミングにおけるXORのTips - Qiita
Bit Twiddling Hacks