C++で方程式 n = x + n⊕x の解の個数を求める方法

本記事では、方程式 n = x + n ⊕ x の解の個数を求める方法を解説します。つまり、与えられた n に対して、この等式を満たす x の値がいくつ存在するかを求める問題です。ここで「⊕」はXOR(排他的論理和)演算を表します。

それでは、具体例を挙げながら、n = x + n ⊕ x の解の個数について詳しく見ていきましょう。

全探索(ブルートフォース)による解法

最もシンプルなのが全探索(ブルートフォース)のアプローチです。与えられた n に対して、x の候補として 0 から順に整数を代入し、等式が成り立つかどうかを1つずつ確認していきます。なお、x の範囲は 0 以上 n 以下に限定できます。n より大きい値を (n ⊕ x) に加算しても、結果が n になることは決してないためです。

例：n = 3 のときの解を1つ求める

x = 0 を代入すると、
    3 = 0 + 3 ⊕ 0
    3 ⊕ 0 = 3 なので、
    3 = 3
    左辺 = 右辺(x = 0 は等式を満たす)
したがって、x = 0 は解のひとつ

C++での実装例(全探索)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n = 3, c = 0;
    for (int x = 0; x <= n; ++x) // x に 0 から n までの値を順に代入
        if (n == x + (n ^ x))    // x が等式を満たすかどうかを判定
            ++c;
    cout << "Number of possible solutions : " << c;
    return 0;
}

出力

Number of possible solutions : 4

これは全探索法によって n = x + n ⊕ x の解の個数を求めるシンプルなC++プログラムです。なお、XOR演算子(^)は加算よりも優先順位が低いため、意図どおりに動作させるには (n ^ x) のように括弧を付ける点に注意しましょう。

効率的な解法(ビット演算を利用)

次に、より効率的なアプローチを見てみましょう。n を2進数で表したときに「1」となっているビット(セットビット)の個数に着目します。等式の性質上、n のあるビットが 1 である場合、そのビットは x 側か n ⊕ x 側のどちらか一方に必ず現れます(1 ⊕ 1 = 0 となるため、両方には立てません)。つまり、n のセットビット1つひとつに対して「x でそのビットを立てるか立てないか」の2通りの選択肢があることになります。したがって、解の個数は 2^(セットビットの個数) として求められます。

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

#include <bits/stdc++.h>
using namespace std;
int main (){
    int n = 3, no_of_setbits = 0;    // n の初期化と、セットビット数のカウント用変数
    while (n != 0){
        no_of_setbits += (n % 2);    // 最下位ビットが 1 かどうかを確認
        n /= 2;
    }
    int result = 1 << no_of_setbits; // 2^セットビット数 で解の個数を計算
    cout << "Number of possible solutions : " << result;
    return 0;
}

出力

Number of possible solutions : 4

計算量

全探索法では、x の候補をすべて試すため、時間計算量は O(n) となります。一方、セットビットの個数を利用する効率的な解法では、n を繰り返し半分にしながら処理を進めるため、時間計算量は O(log n) となり、特に n が大きい場合に大幅な高速化が期待できます。

まとめ

本記事では、方程式 n = x + n ⊕ x の解の個数を求める問題を取り上げました。全探索による素直な解法と、セットビットの個数から答えを一発で導ける効率的な解法の2通りを、C++プログラムとともに解説しました。同じロジックは C、Java、Python など他のプログラミング言語でも同様に実装できます。読者の皆さんの学習の一助となれば幸いです。