C++でXOR演算子を使わずに2つの数値のXORを求める方法

この問題では、2つの整数値 A と B が与えられ、XOR演算子（^）を使用せずに両者のXORを求めることが課題となります。

具体例で問題を確認してみましょう。

入力 : A = 4, B = 5
出力 : 1

解法アプローチ1：ビットごとの演算を利用する

まず、各数値を2進数に変換し、次の真理値表に基づいてビット単位の演算を行う方法があります。

この表は、両方のビットが同じ場合に0、異なる場合に1を返す、まさにXORの動作そのものです。AND・OR・NOTなどの基本的なビット演算だけを組み合わせることで、この結果を実現できます。

実装例

上記の解法の動作を示すプログラムです。

#include <iostream>
using namespace std;
int calcXORwoOperator(int a, int b){
    int xorVal = 0;
    for (int i = 31; i >= 0; i--){
        bool val1 = a & (1 << i);
        bool val2 = b & (1 << i);
        bool xorBit = (val1 & val2) ? 0 : (val1 | val2);
        xorVal <<= 1;
        xorVal |= xorBit;
    }
    return xorVal;
}
int main(){
    int a = 4, b = 5;
    cout<<"XOR of the numbers is "<<calcXORwoOperator(a, b);
   return 0;
}

出力

XOR of the numbers is 1

このプログラムでは、上位ビットから順に各ビットを取り出し、両方のビットが1の場合は0、それ以外の場合はOR演算の結果を設定することで、XORと同等の処理を実現しています。

解法アプローチ2：論理式を利用する（より簡潔な方法）

もうひとつの方法として、2つの数値の対応するビットを1つずつ比較し、XORと同等の演算を行うアプローチがあります。

ポイントとなるのは、次の論理式です。

(a | b) - (a & b) ≡ a ^ b

この式が成り立つ理由は以下の通りです。

• (a | b)：少なくとも片方のビットが立っている位置がすべて1になります。
• (a & b)：両方のビットが立っている共通部分のみが1になります。

ORの結果からANDの結果を引くと、「片方だけが1であるビット」だけが残ります。これはXORの定義と完全に一致します。この式を使えば、ループも不要で、たった1行でXORを求められます。

実装例

上記の解法の動作を示すプログラムです。

#include <iostream>
#include <bitset>
using namespace std;
int calcXORwoOperator(int a, int b) {
   return (a | b) - (a & b);
}
int main(){
   int a = 4;
   int b = 5;
   cout<<"The XOR of both numbers is "<<(bitset<8>(calcXORwoOperator(a, b)));
   return 0;
}

出力

The XOR of both numbers is 00000001

まとめ

XOR演算子を使わずに2つの数値のXORを求めるには、主に2つの方法があります。

1. ビットごとの演算：各ビットを取り出して真理値表に従って計算する。ロジックの理解に役立ちます。
2. 論理式 (a | b) - (a & b)：シンプルかつ効率的で、実務向きの手法です。

どちらの方法もXORの本質である「異なるビットだけが1になる」という性質を活かしたものです。面接や競技プログラミングでも頻出のテーマなので、ぜひ覚えておきましょう。