C++でNとのビット単位AND演算により得られる数値の集合を出力する方法

この問題では、0からnまでの各整数とnをビット単位AND演算（&）したときに得られる値をすべて求め、重複なく出力します。これらの値は、nの2進表現における「1」のビットを組み合わせた部分集合（部分マスク）に相当します。

問題の例

具体例を見ながら概念を理解しましょう。

入力 : N = 4
出力 : 0 4
説明 :
    0 & 4 = 0
    1 & 4 = 0
    2 & 4 = 0
    3 & 4 = 0
    4 & 4 = 4

入力 : N = 6
出力 : 0, 2, 4, 6

N = 6の場合、6は2進数で「110」と表されます。0から6までの各数値と6のANDを取ると、結果は0、2、4、6の4種類のみとなります。これは「110」の各ビットを含めるか除外するかの組み合わせ、つまりnの部分マスクそのものです。

解決アプローチ

この問題を効率的に解くには、ビット演算子を活用します。nから開始し、更新式 i = (i - 1) & n を用いて降順に走査することで、AND演算の結果として現れる値だけを直接取り出せます。通常のデクリメントではなくこの式を使うことで、結果にならない数値をスキップし、無駄な計算を大幅に削減できます。

アルゴリズム

ステップ1 : 更新式 i = (i - 1) & n を使い、nから1までループする
ステップ2 : 各反復で i の値を出力する
ステップ3 : ループ終了後、0 を出力して終了する

実装例

上記のアルゴリズムをC++で実装したプログラムは以下の通りです。

#include <iostream>
using namespace std;
int main() {
    int n = 11;
    for (int i = n; i > 0; i = (i - 1) & n)
        cout << i << " ";
    cout << 0;
    return 0;
}

出力

11 10 9 8 3 2 1 0

n = 11（2進数で「1011」）の場合、11のビットの部分集合となる値が降順に出力されます。この手法の計算量は出力される部分マスクの個数に比例するため、0からnまでを全件走査する方法と比べてはるかに効率的です。