【C++】ビット単位ORがnと等しくなる最大の集合を求める方法

このチュートリアルでは、与えられた数値 n に対して、ビット単位OR（bitwise OR）の結果が n と等しくなる最大の集合を見つけるプログラムを C++ で作成します。

問題の考え方

ある整数 i と n のビット単位ORが n と等しくなるためには、i のセットされているビットがすべて n のセットされているビットに含まれている必要があります。つまり、i は n のビットパターンの「部分集合」であればよいことになります。

解法の手順

• 数値 n を初期化します。
• 0 から n まで繰り返すループを作成します。
  • もし i | n の結果が n と等しければ、i を結果の集合に追加します。
• 最後に結果を出力します。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

void printBitWiseOrSet(int n) {
    vector<int> v;
    for (int i = 0; i <= n; i++) {
        if ((i | n) == n) {
            v.push_back(i);
        }
    }
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << ' ';
    }
    cout << endl;
}

int main() {
    int n = 7;
    printBitWiseOrSet(n);
    return 0;
}

実行結果

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

0 1 2 3 4 5 6 7

解説

n = 7 の場合、7 は2進数で 111 と表されます。したがって、0 から 7 までのすべての整数は 7 のビットパターンの部分集合となり、i | 7 == 7 が常に成立します。そのため、結果として 0 から 7 までのすべての数値が出力されます。

一方、例えば n = 5（2進数で 101）の場合、条件を満たすのは 0, 1, 4, 5 のみとなります。このように、n のビット構成によって結果の集合の大きさが決まります。

まとめ

このアルゴリズムの計算量は O(n) であり、シンプルな線形探索で問題を解くことができます。ビット演算の性質を理解する良い練習問題なので、ぜひさまざまな n の値で試してみてください。

このチュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。