C++で「NとのOR」と「NとのXOR」が等しくなる数をカウントする方法

この記事では、整数 N が与えられたとき、0からNまでの範囲にある数のうち、「その数とNのOR（論理和）の結果」が「その数とNのXOR（排他的論理和）の結果」と等しくなるものを数える方法を解説します。

具体的には、i = 0 から i <= N まで順番に走査し、それぞれの i について条件 (N ^ i) == (i | N) が成立する場合にカウントを1つずつ増やしていきます。

具体例

まずは例を使って問題を理解しましょう。

入力： N = 6
出力： 条件を満たす数の個数：2
説明： 該当する数は 0 と 1 です。

入力： N = 20
出力： 条件を満たす数の個数：8
説明： 該当する数は 0, 1, 2, 3, 8, 9, 10, 11 です。

なぜこの条件が成り立つのか

ビット単位で考えると、ORとXORの結果が一致するのは、i と N の間に共通して1になっているビットが存在しない場合だけです。

• 両方のビットが0 → ORもXORも0（一致）
• どちらか一方だけが1 → ORもXORも1（一致）
• 両方のビットが1 → ORは1、XORは0（不一致）

つまり、この条件は (i & N) == 0 と同値であり、N = 20（2進数で10100）の場合、上位ビットを共有しない 0〜3 と 8〜11 が該当することがわかります。

プログラムのアプローチ

以下のプログラムでは、次の手順で問題を解いています。

• 整数 N を受け取ります。
• 関数 orisXOR(int n) は、引数 n に対して「nとのORがnとのXORと等しくなる数」の個数を返します。
• カウント用変数 count を 0 で初期化します。
• i = 0 から i <= n までループで走査します。
• 各 i について (i | n) == (i ^ n) が成立すれば count をインクリメントします。
• ループ終了後、count に求める結果が格納されているので、それを返して表示します。

サンプルコード

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int orisXOR(int n){
    int count = 0;
    for (int i = 0; i <= n; i++){
        if((n|i)==(i^n))
            { count++; }
    }
    return count;
}
int main(){
    int N = 15;
    int nums=orisXOR(N);
    cout <<endl<<"Count of numbers whose OR with N == XOR with N: "<<nums;
    return 0;
}

実行結果

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

Count of numbers whose OR with N == XOR with N: 1

N = 15 は2進数で 1111 となり、すべての下位4ビットが1のため、0以外の数とは必ずビットが重複します。したがって、条件を満たすのは 0 のみ となり、結果は 1 になります。