皆知の論理演算としては、「論理積」（AND）と「論理和」（OR）が主にあり、「排他的論理和」（XOR）も非常に重要です。
本稿では排他的論理和の意味と応用について解説します。
一、意味
XOR は exclusive OR の略です。英語の exclusive は「専有の、排他的」という意味で、XOR はより純粋な OR 演算と理解できます。
OR 演算の演算子には二つの状況があり、計算結果はtrue。
（1）一方が true で、もう一方が false の場合;
（2）両方が true の場合。
上記の二つの状況を明確に区別する必要がある場合があるため、XOR が導入されました。
XOR は第二种情况を除外し、第一種情况（一方がtrueで他方がfalseである場合）のみtrueを返すため、より純粋なOR演算と見なすことができる。つまり、XOR は主に二つの値が異なるかどうかを判断するために使用される。
XOR は通常、插入記号（caret）^で表される。0をfalse、1をtrueとする場合、XORの演算真値表は以下の通りである。
0 ^ 0 = 0 0 ^ 1 = 1 1 ^ 0 = 1 1 ^ 1 = 0
二、演算法則
XOR演算には以下の演算法則がある。非常に簡単なので、ここでは証明を省略する。
（1）一つの値と自身との演算は常にfalseです。
x ^ x = 0
（2）一つの値と0との演算は常にその値そのものに等しいです。
x ^ 0 = x
（3）交換可能性
x ^ y = y ^ x
（4）結合可能性
x ^ (y ^ z) = (x ^ y) ^ z
三、応用
上記の演算法則に基づいて、排他的論理和演算の多くの重要な応用が得られます。
3.1 計算の簡略化
複数の値の排他的論理和演算は、演算法則に基づいて簡略化できます。
a ^ b ^ c ^ a ^ b = a ^ a ^ b ^ b ^ c = 0 ^ 0 ^ c = c
3.2 値の交換
二つの変数を連続して三回排他的論理和演算を行うことで、値が互いに交換されます。
という二つの変数がxとyで、それぞれの値がaとbである。以下はxとyを三回の排他的論理和演算を行ったもので、コメント部分は各演算後の二つの変数の値である。
x = x ^ y // (a ^ b, b) y = x ^ y // (a ^ b, a ^ b ^ b) => (a ^ b, a) x = x ^ y // (a ^ b ^ a, a) => (b, a)
これは二つの変数の値を交換する最も速い方法で、追加の空間を必要としない。
3.3 暗号化
排他的論理和演算は暗号化に使用できる。
最初のステップでは、平文（text）と鍵（key）を排他的論理和演算することで、暗号文（cipherText）を得る。
text ^ key = cipherText
次に、暗号文と鍵を再び排他的論理和演算することで、平文に戻すことができる。
cipherText ^ key = text
の原理は簡単です。もし平文がxで、鍵がyならば、xがyと2回連続で排他的論理和（XOR）を行うと、x自身が得られます。
(x ^ y) ^ y = x ^ (y ^ y) = x ^ 0 = x
3.4 データバックアップ
排他的論理和はデータバックアップに利用できます。
ファイルxとファイルyを排他的論理和（XOR）すると、バックアップファイルzが生成されます。
x ^ y = z
その後、ファイルxやファイルyが破損したとしても、2つの元のファイルが同時に破損していない限り、もう一方のファイルとバックアップファイルを使って復元できます。
x ^ z = x ^ (x ^ y) = (x ^ x) ^ y = 0 ^ y = y
上記の例ではyが破損した場合、xとzを排他的論理和（XOR）することでyを得られます。
四、面接問題
いくつかの面接のアルゴリズム問題も、排他的論理和（XOR）を使って素早く解くことができます。
以下の問題をご覧ください。
配列には n-1 個の要素があり、これらは 1 から n の整数で、重複していない。欠けている数字を見つけ出してください。
最も速い解決方法は、すべての配列要素（A[0] から A[n-2]）と 1 から n の整数をすべて合わせて、排他的論理和（XOR）を行うことです。
A[0] ^ A[1] ^ ... ^ A[n-2] ^ 1 ^ 2 ^ ... ^ n
上記の式では、各配列要素は 2 回出現します。同じ値の排他的論理和を行うと 0 になります。欠けている数字は 1 回だけ出現するので、最終的に得られるのがその値です。
排他的論理和以外にも、加算でこの問題を解く方法を思いつくかもしれません。
1 + 2 + ... + n - A[0] - A[1] - ... - A[n-2]
しかし、加算は排他的論理和よりも遅く、追加のメモリが必要です。数字が大きい場合、オーバーフローする可能性もあります。
次は似たような問題を出題します。練習として解いてみてください。
配列には n+1 個の要素があり、これらは 1 から n の整数です。ただし、1 つの要素は 2 回出現し、他の要素は 1 回だけ出現します。重複している要素を見つけ出してください。
五、参照リンク
（終）