2つの数のXOR合計が最小になる値を求めるC++プログラム

2つの数 a と b が与えられたとき、ある値 x を選んで (a XOR x) + (b XOR x) の最小値を求めることを考えます。

たとえば、入力が a = 6、b = 12 の場合、出力は 10 になります。x = 4 を選ぶと、(6 XOR 4) + (12 XOR 4) = 2 + 8 = 10 となるからです。

考え方

各ビットの位置ごとに考えてみましょう。

• a と b のビットが同じ（両方とも0、または両方とも1）であれば、x のそのビットを同じ値にすることで、両方のXOR結果はその桁で0になります。
• a と b のビットが異なる場合は、x をどのように選んでも、必ずどちらか一方がその桁で1になります。

したがって、最小値は単純に a XOR b に等しくなります。これが答えです。

アルゴリズム

return a XOR b

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include<bits/stdc++.h>
using namespace std;

int solve(int a, int b){
   return (a^b);
}

int main(){
   int a = 6;
   int b = 12;
   cout << solve(a, b) << endl;
}

入力

6, 12

出力

10

まとめ

この問題のポイントは、x を工夫して選んでも a と b のビットが異なる桁では必ず1が残るという点です。そのため、複雑な探索を行う必要はなく、(a XOR x) + (b XOR x) の最小値は常に a XOR b であることが証明できます。計算量は O(1) と非常に効率的です。