備忘録・ちょっと得した気分になるXORの話

先日、コードテスト試験の練習問題を解いていた時の話。

問題は権利的に書けませんが、その途中で見ていたXORについての得する話がありました。

本題の前に復習。
XOR(排他的論理和)は、真理値表で以下の振る舞いをします。(もっと詳しくはこちら)

入力		出力
A	B	X
0	0	0
0	1	1
1	0	1
1	1	0

で本題。
このXOR、何に使われるかというと、ビット誤り検知や暗号に使います。
詳しくはこちらに譲りますが、XORには以下の性質があります。

A ⊕ B ⊕ B = A ... (1)

これがどのように使えるかというと、
「仲間はずれ抽出」に使えます。

例えば、「1, 2, 3, 2, 1」の要素がある時、全ての要素をビット化すると以下になります。

10進法	2進法(ビット)
1	1
2	10
3	11
2	10
1	1

このビット列を(1)の式に当てはめると、

1⊕ 10 ⊕ 11 ⊕ 10 ⊕ 1 = 11 ... (2)

になります。見ての通り、仲間はずれの3が抽出できました。
ただし、おそらく2つ以上の仲間はずれの抽出はできません。(証明したわけではないです...。)

10進法	2進法(ビット)	XORの結果
初期値	0	0
1	1	1
2	10	11
3	11	0
4	100	100
5	101	1
6	110	111
7	111	0
1	1	1
2	10	11
3	11	0

というわけで、ちょっと得した気分になれるXORの話でした。