PythonによるPDFの各操作のまとめ記事をつくりました

XOR(排他的論理和)の4つの見方

情報理論でよくXORが使われたりするので、4つの使われ方(見方)をまとめました。

XOR(排他的論理和)の演算

XORは以下の真理値表を満たすような論理演算です。

\(a\)\(b\)\(a \oplus b\)
000
011
101
110
XOR演算の真理値表

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って意外と使い道あるんだと思っていただけたら幸いです。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です