排他的論理和 XOR のアルゴリズム

排他的論理和 (XOR; logical exclusive-or) は、片方のオペランドが true の場合だけ結果が true になります。 AND と OR と NOT のみで XOR を表現すると、「(a || b) && !(a && b)」となります。

C++ や Java, C# で XOR を計算するには、「^」演算子を使用します。以下のソースコードは、 C# のサンプルです。

bool[] bits1 = { false, false, true, true };
bool[] bits2 = { false, true, false, true };

/* 「^」演算子で XOR を計算 */
for (int i = 0; i < bits1.Length; ++i)
{
    System.Diagnostics.Debug.WriteLine(string.Format("{0} ^ {1} = {2}",
        bits1[i], bits2[i], bits1[i] ^ bits2[i]));
}

/* AND, OR, NOT のみを利用して XOR を表現 */
for (int i = 0; i < bits1.Length; ++i)
{
    System.Diagnostics.Debug.WriteLine(string.Format("{0} ^ {1} = {2}",
        bits1[i], bits2[i], (bits1[i] || bits2[i]) && !(bits1[i] && bits2[i])));
}

/* [実行結果]
 * False ^ False = False
 * False ^ True = True
 * True ^ False = True
 * True ^ True = False
 */