【図解】bit全探索の動きをみていく

今回はbit全探索についてまとめます。2進数やbit演算に関する知識も浅く復習しますが、このページだけではすべてを伝えきれないので平行して調べていただけたらと思います。

bit全探索とは？

ズバリ、いくつかの候補の中から、それぞれ「選ぶ・選ばない」の2択を選択をしていき、その組み合わせを全列挙することです。イカツい名前ですが、やってることはとても単純なので怖がる必要なないです。

例えば、\(N\)個の数字があり、好きな数字を選べるとします。このとき、総和を\(S\)にするような数字の組み合わせを答えなさい。というような問題に有用です。このような問題は部分和問題と呼ばれます。

それぞれの数字に対して「選ぶ・選ばない」の2通りの選択ができるので、計算量は\(O(2^N)\)になります。注意点としては、\(N\)が20程度までの場合にしか使えないところです。そのため、部分和問題は動的計画法で解くことも多いです。これもイカツい名前ですね。競技プログラミングのアルゴリズムはかっこいい名前が多くて好きです。

bitとは？

よく耳にすると思いますが、コンピュータでは情報を2進数で表しています。bitとは、2進数に直したときの最小単位であり、それが取り得る値は0か1です。コンピュータの内部では、私たちが普段用いている10進数の値を2進数のbitに対応させて処理しています。コンピュータの内部ではONかOFF、もしくは磁石のN極かS極かのような2通りの判断しかできないためです。

たとえば、0から7の数字は以下のような2進数(bit列)に対応しています。

bit全探索ではbit列の「1を選ぶ、0を選ばない」に対応づけて処理します。また、1のbitに対して、ビットが立っている、というような表現をすることがあります。

bit演算

bitを操るにはbit演算という処理を行います。今回扱うものには、主に論理積とシフト演算があります。

論理積

論理積は2つのbit列に対して行う演算です。C言語では「&」を使います。二つのbitを見比べ、どちらも1であれば値を1にし、それ以外は0になります。

シフト演算

シフト演算は、ビットを横にずらすことをいいます。実際には論理シフトと算術シフトがありますが、今回は気にせず大丈夫です。単に符号ビットを維持するかしないかの違いですが、興味のある方は調べてみてください。

C言語では「>>」または「<<」を用います。右シフトか左シフトかの違いです。「1 << n」と記述することは、1を左にnだけシフトさせることになります。シフト演算では、左シフトでは0で埋められ、右シフトでは情報が捨てられることになります。1つ左シフトすることは値を2倍することと同様です。2つシフトする場合は\(2^2 = 4\)倍されます。しかし、右シフトすることは単に割り算とは限りません。これは右シフトでは情報が捨てられることがあるためです。

簡単なbit全探索を行ってみる

日本語ばかりで退屈だったと思うので、早速、例題とソースコードを見てみたいと思います。

例題

\(N\)個の数字が与えられます。この中からいくつか選び、総和を\(S\)にすることができる組み合わせを数えてください。

入力

N S
a1 a2 ... an

出力

総和を\(S\)にすることができる数字の組み合わせ数を出力せよ。

例1

4 11
4 5 2 7

2

\(a = \{4, 5, 2\}\) もしくは \(a = \{4, 7\}\) のように選べば総和を11にできます。

例2

5 5
0 1 2 6 8

0

どのように選んでも総和を5にすることはできません。

ソースコード(bit演算のみ)

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

int main()
{
	int N, S, cnt = 0;
	cin >> N >> S;
	vector<int> a(N);

	// 入力
	for (int i = 0; i < N; i++) cin >> a.at(i);

	// 0, 1, 2, ... , (2^N)-1 まで調べ上げる
	for (int bit = 0; bit < (1 << N); bit++){
		int sum = 0;
		for (int i = 0; i < N; i++){
			// とあるbitが1なら、対応する数字を加算
			if (bit & (1 << i)) sum += a[i];
		}

		// すべての桁について調べ上げたのち、
		// 条件を満たす組み合わせならカウントしておく
		if (S == sum) cnt++;
	}
	// 条件を満たす組み合わせ数を出力
	cout << cnt << endl;

	return 0;
}

解説

まず、全探索する範囲を決めます。それがこの記述箇所です。

	// 0, 1, 2, ... , (2^N)-1 まで調べ上げる
	for (int bit = 0; bit < (1 << N); bit++){

bit < (1 << N) の箇所は、\(2^N\)まで探索しますよ、という意味です。選ぶ・選ばないで全通りが\(2^N\)になるということからきています。例えば、\(N = 3\) の場合では、bit \(< 2^3 = 8\)、つまり bit \(= 0, 1, 2, 3, 4, 5, 6, 7\)までループが回されることになります。

		for (int i = 0; i < N; i++){
			// とあるbitが1なら、対応する数字を加算
			if (bit & (1 << i)) sum += a[i];
		}

ここがなかなかわかりづらい部分ではあるのですが、最下位bitから最上位bitまでの「1であるbit」を調べています。bit全探索では、bitの各桁をN個の数字と対応づけて処理していきます。この「1であるbit」の部分を、「選んだ数字」として加算している訳です。

具体的に、例題の例1について動かしたプログラムでは、以下のような挙動になります。

bit = 6 (スライド25 – 28) について見てみます。

bit = 6 を2進数のbit列に直すと、(0 1 1 0)になります。まず、i = 0において、bit & (1 << i) = (0 1 1 0) & (0 0 0 1) を計算します。値は0であり、条件式はFalseになります。ifやwhileなどの条件式では、条件式の値が0においてFalse, それ以外ではTrueとして処理されます。(厳密ではないですが、そう思っておいて問題ないです。)

よって7は選ばないことになり、sumにはまだ何も足しません。

次に、i = 1において、bit & (1 << i) = (0 1 1 0) & (0 0 1 0) = (0 0 1 0)になり、この条件式はTrueになります。つまり、2を選ぶこととして、sumに2を足します。

i = 2において、bit & (1 << i) = (0 1 1 0) & (0 1 0 0) = (0 1 0 0) であり、条件式はTrueになります。つまり、さらに5も選ぶこととして、sumに5を足して sum = 7とします。

i = 3において、bit & (1 << i) = (0 1 1 0) & (1 0 0 0) = (0 0 0 0) であり、条件式はFalseです。そのため4は選ばれないことになり、sumには何も足しません。

ここまでで、bit = 6に対するすべての数字について調べ終わりました。その結果、\( \{5, 2\} \)を選んだ場合はsum = 7となり、\(S = 11\)とは等しくなりません。この組み合わせは要求を満たさないため、カウントせずbit = 7へと進むことになります。

bitをさらに進めて、bit = 9 (スライド37 – 40) についてみてみます。

bit = 9, i = 0において、bit & (1 << i) = (1 0 0 1) & (0 0 0 1) = (0 0 0 1) となり、条件式はTrueになります。よって7を選ぶこととして、sum += 7 をします。

i = 1において、bit & (1 << i) = (1 0 0 1) & (0 0 1 0) = (0 0 0 0) となり、条件式はFalseになります。よって2は選ばす、sum = 7のままです。

i = 2において、bit & (1 << i) = (1 0 0 1) & (0 1 0 0) = (0 0 0 0) となり、条件式はFalseになります。よって、5も選ばす、sum = 7のままです。

i = 3において、bit & (1 << i) = (1 0 0 1) & (1 0 0 0) = (1 0 0 0) となり、条件式はTrueです。よって、4を選ぶこととして、sum = 11となります。

ここで、bit = 9においてすべての数字に対して調べ終わりました。選んだ数字の組み合わせは \(\{ 4, 7\}\) であり、sum = 11となりました。 この組み合わせは \(S = 11\) と一致します。したがってcntを1つ増加させ組み合わせ数を記録しておきます。

最終的にbit = 15まで調べ上げていくと、先ほどのbit = 9 と bit = 14 において選んだ数字の総和が\(S\)と一致することがわかりました。

よって出力するべき値はcnt = 2です。

このようにして、bit全探索は「すべての組み合わせをbitを使って探索していく」ことで解を見つけ出します。

bitsetを使う方法

以上ではbit演算だけで実装しましたが、C++のSTL（標準ライブラリ）であるbitsetを用いる方法もあります。bitsetでよく使うメンバ関数を以下に挙げます。

実際に、先ほどのソースコードをbitsetを使って書き直すと以下のようになります。

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

int main()
{
	int N, S, cnt = 0;
	cin >> N >> S;
	vector<int> a(N);

	// 入力
	for (int i = 0; i < N; i++) cin >> a.at(i);

	// 0, 1, 2, ... , (2^N)-1 まで調べ上げる
	for (int bit = 0; bit < (1 << N); bit++){
		int sum = 0;
		bitset<20> bst(bit);
		for (int i = 0; i < N; i++){
			// とあるbitが1なら、対応する数字を加算
			if (bst.test(i)) sum += a[i];
		}

		// すべての桁について調べ上げたのち、
		// 条件を満たす組み合わせならカウントしておく
		if (S == sum) cnt++;
	}
	// 条件を満たす組み合わせ数を出力
	cout << cnt << endl;

	return 0;
}

bitset<20> bst(bit);では、bstが、bitの2進数表記で初期化されることに注意してください。

注意点とまとめ

冒頭でも書きましたが、その性質上、bit全探索の計算量は \(O(2^N)\)となってしまうため、部分和問題 ==> bit全探索で解く！とはなりません。一般に、\(N = 20 ～ 25\) 程度であればbit全探索で解けると思っていいでしょう。競技プログラミングではもちろん、システム開発を行う場合でも制約や条件をよく確認して、どの程度の計算量であれば間に合うのかを判断することが重要です。