こんにちは、42Tokyoのkharuyaです🙇
アルゴリズムの勉強をしっかりやろうと思い、最近AtCoderに取り組んでいるので、とりあえずビット全探索という探索法の一つについて簡単にまとめてみました。

ビット全探索（Bit Full Search）とは

ビット全探索とは、$N$ 個の要素があるとき、それぞれの要素について「選ぶ」か「選ばない」かの2通りを考え、全 $2^N$ 通りの組み合わせをビット演算を用いて高速に全列挙・探索する手法です。

競プロ（競技プログラミング）の基本的な力まかせ探索（全探索）アルゴリズムの一つで、主に $N$ が20程度の問題に有効です。

基本的な考え方

例題があったほう理解しやすいと思うので、 おにぎりの例題 を用いて説明していきます。

【例題】 おにぎりのトッピングの組み合わせ一覧表

$N=3$ つの要素（A: エビ、B: カニ、C: 肉）から、好きな具材を選べる（複数選択も可）とすると、全パターン数は $2^3 = 8$ 通り（10進数の 0〜7）となります。
各ビットを 「1 = トッピングする」「0 = しない」 と定義すると、ループ変数（10進数）と実際の選択状態は以下のように完全に対応します。

10進数	2進数 (CBA)	C (肉)	B (カニ)	A (エビ)	選択されたトッピング	合計個数
0	000	0 (×)	0 (×)	0 (×)	なし（抜き）	0個
1	001	0 (×)	0 (×)	1 (〇)	エビ	1個
2	010	0 (×)	1 (〇)	0 (×)	カニ	1個
3	011	0 (×)	1 (〇)	1 (〇)	エビ, カニ	2個
4	100	1 (〇)	0 (×)	0 (×)	肉	1個
5	101	1 (〇)	0 (×)	1 (〇)	エビ, 肉	2個
6	110	1 (〇)	1 (〇)	0 (×)	カニ, 肉	2個
7	111	1 (〇)	1 (〇)	1 (〇)	エビ, カニ, 肉	3個

実装に使う主要な記法 (C++ / Python)

ビット全探索を理解するために必須の演算子です。

操作	記法 (C++/Python)	意味
左シフト	1 << n	$2^n$ を計算する（全パターンの数）
論理積 (AND)	i & (1 << j)	i 番目のパターンの j 番目のビットが立っているか判定

実装テンプレート (C++)

最も標準的な書き方です。

#include <iostream>
#include <vector>

void bit_search(int n) {
    // 1. 全パターン (2^n 通り) をループ
    for (int bit = 0; bit < (1 << n); ++bit) {
        std::vector<int> selection;

        // 2. 各要素について、bitが立っているか確認
        for (int i = 0; i < n; ++i) {
            if (bit & (1 << i)) { // i番目の要素が選ばれているか
                selection.push_back(i);
            }
        }

        // 3. ここで選ばれたパターンの処理を行う
        std::cout << "Pattern " << bit << ": ";
        for (int x : selection) std::cout << x << " ";
        std::endl(std::cout);
    }
}

計算量

計算量：$O(N \cdot 2^N)$
$N=10$ のとき：$10 \cdot 2^{10}$ → 約 1 万（余裕）
$N=20$ のとき：$20 \cdot 2^{20}$ → 約 2000 万（1秒以内の限界目安）
$N=30$ のとき：$30 \cdot 2^{30}$ → 約 300 億（実行不可）

想定される問題例一覧

前述した通り、ビット全探索が有効なのは、要素数 $N$ が 20〜25以下 の時です。

• 部分和問題:「$N$個の数字の中からいくつか選んで、合計を $K$ にできるか？」
• スイッチ・電球問題:「$N$個のスイッチがあり、それぞれ押すと特定の電球が反転する。全ての電球を点灯させる組み合わせは？」
• コスト最適化:「$N$個の商品があり、それぞれ価格と満足度が設定されている。予算内で満足度を最大化する組み合わせは？」
• グリッドの塗り分け:「$H \times W$ のマス目を白黒で塗る時、特定の条件を満たす塗り方は？」