Posted at

bit全探索について簡単にまとめる

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


bit全探索とは

bit全探索とは、bit演算を使って全探索をする方法。bit全探索を使えば、部分集合を全パターン列挙することができる。

例えばAtCoderの「C - たくさんの数式 / Many Formulas」のような問題で、各文字列中のどこに+を入れるかというパターンを簡単に全探索できる。


bit全探索の例

例のコードは以下のようになる。(参考:ビット演算 (bit 演算) の使い方を総特集!


#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 が bit に入るかどうか
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)の部分だと思う。この部分は結論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 が bit に入るかどうか

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

8(0b00001000)と4(0b00000100)であれば、同じビット位置に1が来ることがないため、結果は0(0b00000000)となる。他にも7(0b00000111)と4(0b00000100)であれば結果は4(0b00000100)になる。

これを踏まえると、冒頭のサンプルコードであるbit & (1<<i)は、bitに0~7が来て、その数でそれぞれiを0~2で繰り返す。

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


bit全探索まとめ

分かりやすい考え方は「bit & (1<<i)はbitを2進数で表したとき、立っているビット部分を列挙できる」ということ。

ただこの説明で少し前の自分が理解できるかどうかは怪しい。やはり実際に手を動かして試すのが一番良い。