情報理論でよくXORが使われたりするので、4つの使われ方(見方)をまとめました。
XOR(排他的論理和)の演算
XORは以下の真理値表を満たすような論理演算です。
\(a\) | \(b\) | \(a \oplus b\) |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
XOR演算の4つの見方(使い方)
aとbが異なるかどうか
0同士または1同士のXOR演算の結果は0で、0と1のXOR演算の結果は1です。
つまり、
\[ a \oplus b = \begin{cases} 0 & (aとbが同じ) \\ 1 & (aとbが異なる) \end{cases} \]となります。
これは例えばハミング距離などに用いられる性質です。
1の数が偶数か奇数か
以下のように0か1の値をとる\(x_i\)をn個並べてXOR演算した結果を考えます。
\[ x_1 \oplus x_2 \oplus \cdots \oplus x_n \]
- 0を何回XOR演算しても0
- 0と1をXOR演算すると1
- 1同士のXOR演算をすると0
この特徴を踏まえると、
1の数が偶数個なら0
1の数が奇数個なら1
になることがわかります。
0と1を反転させる
反転させたいビットaに対して
\(a \oplus 1\)とすると、
\[0 \oplus 1 = 1\]
\[1 \oplus 1 = 0\]
より、aの値(0か1)は反転します。
一方で、
\(a \oplus 0\)の場合は
\[0 \oplus 0 = 0\]
\[1 \oplus 0 = 1\]
となり、aの値は変化しません。
足して2で割った余りとみなせる
\(a \oplus b\)の値は\(a + b\)の値を2で割った余りの値であるという見方もできます。
\[a + b \pmod 2\]
0+0と1+1をそれぞれ2で割った余りは0で、1を2で割った余りが1であることに注目するとたしかにそうなっています。
排他的論理和を初めて知ったときはこんなのどこで使うんだよと思っていましたが、わざわざ論理演算として定義されているだけあって意外と便利なんだなと最近になって知りました。
この記事でXORって意外と使い道あるんだと思っていただけたら幸いです。