C++で和とXORが等しくなる整数の個数を求めるアルゴリズム

問題概要

この問題では、整数 n が与えられます。i = 0 から n までの範囲において、加算結果とXOR（排他的論理和）の結果が一致する、すなわち (n + i) = (n ^ i) を満たす整数 i の個数を求めるプログラムを作成します。

入出力例

入力: n = 4

出力: 4

説明:

i = 0 から n までのすべての値を確認すると、次のようになります。

したがって、条件を満たす整数の個数は 4 となります。

解法アプローチ

最もシンプルな解法は、すべての i について (n + i) と (n ^ i) を実際に計算し、両者を比較して等しくなる場合だけカウントを増やしていく方法です。この方法の計算量は O(n) です。

アルゴリズム

ステップ1: i = 0 から n まですべての値についてループします。

ステップ1.1: (n + i) の値を計算します。

ステップ1.2: (n ^ i) の値を計算します。

ステップ1.3: 手順1.1と1.2で得た値を比較します。
ステップ1.4: 両者が等しければ、カウントを1増やします。

ステップ2: 最終的なカウントを出力します。

解法の動作を示すC++プログラム

実装例

#include <iostream>
using namespace std;

int main() {

    int n = 5;
    int counter = 0;
    for(int i=0; i<=n; i++ )
       if ( (n+i) == (n^i) )
          counter++;
    cout<<"The count of integers with equal sum and XOR is "<<counter;
    return 0;
}

出力

The count of integers with equal sum and XOR is 2

より効率的な解法

上記の方法でも正しく答えを求められますが、ビット演算の性質を利用すると、さらに効率よく解くことができます。

n ^ i = n + i が成り立つとき、必ず n & i = 0 となります。

これは、加算において「n + i = (n ^ i) + 2 × (n & i)」という関係が常に成り立つことから説明できます。つまり、繰り上がり（キャリー）が一切発生しない場合にのみ、加算結果とXORの結果が一致するのです。

n & i = 0 となるためには、n と i の間で「セットされたビット」と「セットされていないビット」が互いに反対の位置に配置されている必要があります。言い換えると、n のビットが 0 になっている位置については、i の対応するビットは 0 でも 1 でも自由に選べるため、答えは 2（n のセットされていないビットの個数）乗 になります。

効率的な解法のC++実装例

#include <iostream>
using namespace std;

int countValuesWithEqualSumXOR(int n) {

    int countUnSetBits=0;
    while (n) {
        if ((n & 1) == 0)
            countUnSetBits++;
        n=n>>1;
    }
    return 1 << countUnSetBits;
}

int main()
{
    int n = 6;
    cout<<"The count of integers with equal sum and XOR is "<<countValuesWithEqualSumXOR(n);
    return 0;
}

出力

The count of integers with equal sum and XOR is 2

まとめ

全探索では O(n) の計算量が必要ですが、「n & i = 0」という性質を使えば、n のセットされていないビットを数えるだけで、答えを O(log n) で求められます。たとえば n = 6（2進数で 110）の場合、セットされていないビットは 1 個なので、答えは 2¹ = 2 となり、実際の出力と一致します。