問題は権利的に書けませんが、その途中で見ていたXORについての得する話がありました。
本題の前に復習。
XOR(排他的論理和)は、真理値表で以下の振る舞いをします。(もっと詳しくはこちら)
で本題。
このXOR、何に使われるかというと、ビット誤り検知や暗号に使います。
詳しくはこちらに譲りますが、XORには以下の性質があります。
A ⊕ B ⊕ B = A ... (1)
これがどのように使えるかというと、
「仲間はずれ抽出」に使えます。
例えば、「1, 2, 3, 2, 1」の要素がある時、全ての要素をビット化すると以下になります。
このビット列を(1)の式に当てはめると、
1⊕ 10 ⊕ 11 ⊕ 10 ⊕ 1 = 11 ... (2)
になります。見ての通り、仲間はずれの3が抽出できました。
ただし、おそらく2つ以上の仲間はずれの抽出はできません。(証明したわけではないです...。)
というわけで、ちょっと得した気分になれるXORの話でした。