C++でXとの和がXORに等しい数をカウントする方法

整数Xが与えられたとき、0からXまでの範囲にある数のうち、「その数とXの和」が「その数とXのXOR（排他的論理和）」と等しくなるものをすべて見つけ、その個数を求めるのが本記事のテーマです。

最も基本的なアプローチは、i=0からi=Xまで順に調べ、各iについて「i + X == i ^ X」という等式が成り立つかどうかを確認することです。条件を満たすたびにカウントを増やしていき、最終的なカウントが答えとなります。

入出力例

• 入力 − X = 6

• 出力 − Xとの和がXORに等しい数の個数: 2

• 説明 − 条件を満たすのは0と1のみです。

• 入力 − X = 20

• 出力 − Xとの和がXORに等しい数の個数: 8

• 説明 − 該当する数は 0, 1, 2, 3, 8, 9, 10, 11 の8個です。

アルゴリズムの手順

• 整数Xを受け取ります。

• 関数sumisXOR(int x)は、xとの和がxとのXORに等しい数の個数を計算して返します。

• カウント変数の初期値を0に設定します。

• i=0からi=xまでforループで走査します。

• i+x == i^x が成立する場合はカウントを1増やします。

• ループが終了した時点で、countには求める個数が格納されています。

• countを返し、結果を出力します。

C++での実装例

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int sumisXOR(int x){
    int count = 0;
    for (int i = 0; i <= x; i++){
        if((i+x)==(i^x))
            { count++; }
    }
    return count;
}
int main(){
    int X = 15;
    int nums=sumisXOR(X);
    cout <<endl<<"Xとの和がXORに等しい数の個数: "<<nums;
    return 0;
}

出力結果

上記のコードを実行すると、次のような出力が得られます −

Xとの和がXORに等しい数の個数: 1

補足：なぜ和とXORが一致するのか

i + x == i ^ x が成り立つのは、iとxが共通して1となっているビットを持たない場合、すなわち (i & x) == 0 が成立するときだけです。共通のビットがない場合、加算の際に桁上がり（キャリー）が発生しないため、和とXORの結果が一致します。

この性質を利用すると、全探索を行わずに答えを直接求めることも可能です。Xのビットが0になっている位置には自由にビットを配置できるため、答えは「Xにおける0のビットの個数」をnとしたときの 2^n となります。例えばX=20（2進数で10100）の場合、0のビットは3個なので 2^3 = 8 個となり、先ほどの例の結果と一致します。