C++で(n XOR x)=(n − x)を満たすx≤nの値の個数を求める方法

問題概要

整数 n が入力として与えられます。このとき、条件 (n XOR x) = (n − x) を満たす値 x のうち、x が範囲 [0, n] に含まれるものの個数を求めるのが目標です。

入出力例

入力 − n = 10

出力 − (n XOR x) = (n − x) を満たす x ≤ n の値の個数 − 4

説明 − 10 xor x = 10 − x を満たす x の値は、0、2、8、10 の 4 つです。

入力 − n = 15

出力 − (n XOR x) = (n − x) を満たす x ≤ n の値の個数 − 16

説明 − 15 xor x = 15 − x を満たす x の値は、0 から 15 までのすべての整数(合計 16 個)です。

アプローチ 1: 全探索(素朴な方法)

for ループを使い、i = 0 から i ≤ n まで順番に走査します。各 i を候補となる x とみなし、(n − i == (n ^ i)) が成立するかどうかを判定します。成立していればカウントを 1 増やします。

アルゴリズムの手順

• 整数変数 n を入力として受け取ります。
• 関数 count_values(int n) は、条件を満たす x の個数を返します。
• count の初期値を 0 とします。
• i = 0 から i ≤ n までループし、n − i == (n ^ i) が真であれば count をインクリメントします。
• count を結果として返します。

アプローチ 2: 効率的な方法(ビット演算を利用)

まず n を 2 進数表現に変換して考えます。1 ビットごとの挙動を調べると、次のことが分かります。

• n のビットが 1 の場合:x のビットが 0 でも 1 でも、XOR の結果と減算の結果は一致します。
• n のビットが 0 の場合:x のビットが 1 だと減算時に桁借り(ボロー)が発生し、XOR の結果と一致しなくなります。

つまり、条件を満たす x は「n の 1 になっているビットだけを選んで 1 にした値」(n の部分マスク)でなければなりません。したがって、n の 2 進表現に含まれる 1 の個数を p とすると、条件を満たす x の個数は 2^p 通りになります。

アルゴリズムの手順

• 整数変数 n を入力として受け取ります。
• count の初期値を 0 とします。
• bitset<8>(n).to_string() を使って n を 2 進数の文字列に変換します。
• length = number.length() として文字列長を取得します。
• i = 0 から i < length まで文字列を走査し、文字が '1' であるたびに count をインクリメントします。
• count = pow(2, count) として、条件を満たす x の総数を求めます。
• count を結果として返します。

サンプルコード(全探索)

#include<bits/stdc++.h>
using namespace std;
int count_values(int n){
    int count = 0;
    for (int i = 0; i <= n; i++){
       if (n - i == (n ^ i)){
          count++;
       }
    }
    return count;
}
int main(){
    int n = 25;
    cout<<"(n XOR x) = (n − x) を満たす x ≤ n の値の個数: "<<count_values(n);
    return 0;
}

出力

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

(n XOR x) = (n − x) を満たす x ≤ n の値の個数: 8

サンプルコード(効率的な方法)

#include<bits/stdc++.h>
using namespace std;
int count_values(int n){
    int count = 0;
    string number = bitset<8>(n).to_string();
    int length = number.length();
    for (int i = 0; i < length; i++){
       if (number.at(i) == '1')
          { count++; }
    }
    count = (int)pow(2, count);
    return count;
}
int main(){
    int n = 25;
    cout<<"(n XOR x) = (n − x) を満たす x ≤ n の値の個数: "<<count_values(n);
    return 0;
}

出力

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

(n XOR x) = (n − x) を満たす x ≤ n の値の個数: 8

計算量の比較と注意点

全探索の時間計算量は O(n) であるのに対し、効率的なアプローチは n のビット長に比例する O(log n) で済みます。n が大きくなるほど後者が圧倒的に有利です。なお、bitset<8> は 8 ビット(最大 255)までしか扱えないため、より大きな n を処理する場合は bitset のテンプレート引数を適切に大きくしてください。