競プロとかで毎回bit全探索を調べ直しているのでまとめる。

bit全探索とは

bit全探索とは、bit演算を使って全探索をする方法。bit全探索を使えば、部分集合を全パターン列挙することができる。
例えばAtCoderの「C - たくさんの数式 / Many Formulas」のような問題で、各文字列中のどこに+を入れるかというパターンを簡単に全探索できる。

bit全探索の例

例のコードは以下のようになる。（参考：ビット演算 (bit 演算) の使い方を総特集！ - Qiita）


#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 3;

    // {0, 1, ..., n-1} の部分集合の全探索
    for (int bit = 0; bit < (1<<n); ++bit) {
        vector<int> S;
        for (int i = 0; i < n; ++i) {
            if (bit & (1<<i)) { // 列挙に i が含まれるか
                S.push_back(i);
            }
        }

        cout << bit << ": {";
        for (int i = 0; i < (int)S.size(); ++i) {
            cout << S[i] << " ";
        }
        cout << "}" << endl;
    }
}

標準出力は以下のようになる。


0: {}
1: {0 }
2: {1 }
3: {0 1 }
4: {2 }
5: {0 2 }
6: {1 2 }
7: {0 1 2 }

bit全探索のコード解説

一つずつ上記のコードを解説していく。まずは最初のfor文を見てみる。


// {0, 1, ..., n-1} の部分集合の全探索
for (int bit = 0; bit < (1<<n); ++bit) {
  //
}

見慣れないのはおそらく(1<<n)の部分だと思う。(1<<n)は2^nと覚えよう。2^nは全パターン数と一致する。

<<という演算子はビット演算子で、ビット（2進数）を左へシフトする。int型は透過的に整数として扱えるが、実際に内部ではbitで管理されている。例えば3を8bitで保持するのであれば、0b00000011になる（2進数は先頭に0bをつける）。

そして1 (0b00000001)を左へ3ビットシフトする場合は1<<3と書き、結果は8(0b00001000)となる。

AND演算

次にこの部分を見る。


if (bit & (1<<i)) { // 列挙に i が含まれるか

まずは(1<<i)この部分。これは先ほど説明した通り、iが3なので2^3で8となる。
&の部分はAND演算、つまり「両方のビットが 1 のときのみ結果が 1 になるビット演算」である。

出力が7: {0 1 2 }となる場合は、bitが7 (0b00000111)である。というのも、どのビット位置（0~2番目）にもビットが立っているため、iが0~2どれであってもAND演算子ではtrueになり、全パターンである0 1 2を列挙することになる。
逆に4: {2 }の場合は4 (0b00000100)は右から3番目にしかビットが立ってないため、0~2の内、3番目である2しか列挙しないことになる。

このようにbitの特性を活かして全探索することができる。

bit全探索まとめ

(1<<n)は2^nと覚える
(bit & (1<<i))はAND演算子であり、bitの特性を活かして列挙することができる

実際に手を動かして試すのが一番分かりやすい。