xorの性質 | Notion

2n ⊕ (2n + 1) = 1
4n ⊕ (4n+1) ⊕ (4n+2) ⊕ (4n+3) = 0
- 証明1 (bitごとに考える)
  - 4n, 4n+1, 4n+2, 4n+3 の（2進数の）1桁目と2桁目は 0 ⊕ 1 ⊕ 2 ⊕ 3 = 0 となる
  - （2進数の）3桁目以降はすべて一致しているので打ち消して 0 になる。
- 証明2
  - 4n ⊕ (4n+1) = 1, (4n+2) ⊕ (4n+3) =1 から従う
- 同様に (4n-2) ⊕ (4n-1) ⊕ 4n ⊕ (4n+1)= 0 も成り立つ
- (4n -1) ⊕ 4n ⊕ (4n+1) ⊕ (4n+2) = 0 は成り立たない
x ⊕ x = 0
- 特に偶数個は打ち消しあう。奇数個の場合は1個残る。
- 出題例: ARC168 B - Arbitrary Nim
- 参考: Zobrist Hash (ハッシュ)
x ⊕ y = x ⊕ z ならば y = z
- 不偏ゲームでこの対偶「y ≠ z ならば x ⊕ y ≠ x ⊕ z」がよく出てくる (xor sum が変化するという話に使える。)
- 証明: 両辺に x を xor として加えれば良い。
- 一般にアーベル群の性質は成り立つ。
$0 \oplus 2^n-1 = 1 \oplus 2^n -2 =2 \oplus 2^n-3 =\cdots = 2^n-1$
- 補数と関係ある？
$a \oplus b = \operatorname{mex}(\{ a' \oplus b \mid 0 \leq a' < a\} \cup \{ a \oplus b' \mid 0 \leq b' < b\} )$
- 参考: Sprague Grundy Theorem, Nimber