競技プログラミングや、速度が求められる処理を書く場面では、すべての組み合わせを試したいという状況がよくあります。
配列やフラグを使って組み合わせを管理しようとすると、速度が遅くなります。
そこで役に立つのが、bit全探索のアルゴリズムです。
CPUはビット演算がとても得意で、二者択一のものをビットの各桁で表すことで、2^Nの組み合わせを最小限のコストで高速に列挙できます。
本記事ではC++によるbit全探索の基本の書き方と、高速探索が出来る理由について紹介します。
前提知識
-
C++の基礎構文を理解している - ビット演算について理解している
ビット演算の基本についてまだの方は、上記の記事を先に読むことを推奨します
bit全探索とは
bit全探索(bitmask enumeration)とは、N個要素の選ぶ/選ばないを、0/1のビットで表し、すべての組み合わせを列挙する技法のことです。
例えば、N = 3の場合を考えてみます。
各要素に対して各桁を割り当て、0の場合は選ばない、1の場合は選ぶとして、表を作成してみます。
| 整数 | 2 進数 | 意味 |
|---|---|---|
| 0 | 000 | 何も選ばない |
| 1 | 001 | 要素 0 を選ぶ |
| 2 | 010 | 要素 1 を選ぶ |
| 3 | 011 | 要素 0,1 を選ぶ |
| 7 | 111 | 全部選ぶ |
このように、ビットの各桁をbool値(選ぶ/選ばない)に見立てることで、整数一つで部分集合を表現することが出来るのです。
もちろん、bool値の配列で同じものを表現することも可能ですが、競技プログラミングなどの速度が求められる場面では、ビット演算が圧倒的に高速なために重宝されます。
サンプルコード
//---------------------------------------------------------------------
//! @file main.cpp
//! @brief ビットマスクを用いて部分集合を列挙するサンプルコード
//! @author つきの
//---------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <bitset>
// エントリポイント
int main() {
//---------------------------------------------------------------------
// 要素数 N と要素の値を定義
//---------------------------------------------------------------------
constexpr int N = 3;
//---------------------------------------------------------------------
// 部分集合を列挙するための配列
//---------------------------------------------------------------------
std::vector<int> a = { 10, 20, 30 };
//---------------------------------------------------------------------
// 2^N 通りの部分集合を列挙
//---------------------------------------------------------------------
for (int mask = 0; mask < (1 << N); mask++) {
//---------------------------------------------------------------------
// 現在のビットマスク(整数と二進数)を表示
//---------------------------------------------------------------------
std::cout << "mask = " << mask
<< " bits = " << std::bitset<N>(mask) << " (";
//---------------------------------------------------------------------
// 選ばれている要素を表示
//---------------------------------------------------------------------
for (int i = 0; i < N; i++) {
// i 番目の要素が選ばれているかをビットマスクで判定
if (mask & (1 << i)) {
// i 番目の要素が選ばれている場合は値を表示
std::cout << a[i] << " ";
}
}
std::cout << ")\n";
}
}
mask = 0 bits = 000 ()
mask = 1 bits = 001 (10 )
mask = 2 bits = 010 (20 )
mask = 3 bits = 011 (10 20 )
mask = 4 bits = 100 (30 )
mask = 5 bits = 101 (10 30 )
mask = 6 bits = 110 (20 30 )
mask = 7 bits = 111 (10 20 30 )
maskの回し方
まず、1 << Nは、1をNビット分左へずらすという意味になります。
| N | (10進数)1 << N | 2進数（ビット列） |
|---|---|---|
| 0 | 1 | 000001 |
| 1 | 2 | 000010 |
| 2 | 4 | 000100 |
| 3 | 8 | 001000 |
| 4 | 16 | 010000 |
| 5 | 32 | 100000 |
| 6 | 64 | 1 000000 |
以下のコードであれば
for (int mask = 0; mask < (1 << N); mask++) {
// 中略
}
(1 << N)により、1をN分だけ左にずらした数、つまり2^Nまでループを回すという意味になります。
ビット判定
//---------------------------------------------------------------------
// 選ばれている要素を表示
//---------------------------------------------------------------------
for (int i = 0; i < N; i++) {
// i 番目の要素が選ばれているかをビットマスクで判定
if (mask & (1 << i)) {
// i 番目の要素が選ばれている場合は値を表示
std::cout << a[i] << " ";
}
}
まず、(1 << i)とは、i(iの最大値はN)分だけ1を左へずらす、要は右からi桁目のビットのみが1の値になった整数ということになります。
mask & (1 << i)は、&演算により、両方のビットが1である場合のみ1(true)になります。
(1 << i)は、右からi桁目のビット以外は0であるため、mask & (1 << i)全体でみると、maskの右からi番目のビットが1ならばtrueで0ならばfalseということになります。
上記のようなアルゴリズムにより、int型の変数一つで、i番目の要素が選ばれているかの全組み合わせを探索することが出来ます。
bit全探索の限界
bit全探索は強力な手法ですが、計算量が2^N と指数的に増加するため、扱えるNには限界があります。
一般的には、N <= 20が約100万通りで、1秒以内で十分処理できる範囲であるため、実用的なラインとされています。
これを超える場合は、また条件によって違ったアルゴリズムを使用する必要があります。
総括
-
bit全探索のアルゴリズムを使用することで、高速全探索を実現することができる -
論理積を使うことで、各桁を各要素の組み合わせに見立てたビット判定を行うことが出来る -
速度の問題で、N <= 20前後が、一般的に実用的な範囲とされている