bit全探索について

APG4bを進めていく最中、bitを用いて通りある問題を解いていくbit全探索というアルゴリズムに触れたので、自分なりの解釈で解説していこうと思います。

bit全探索とは

0と1の羅列である二進数をフラグに見立てて探索するアルゴリズムの一種です。
計算量がとなるので、Nの数があまり大きくない問題にしか使えません。

bit全探索で必要となる知識

シフト演算

シフト演算はビット列を右、もしくは左にN回ずらし、数値を倍、もしくはにするものです。
ずらした結果、用意した列に収まりきらなかったビットは破棄され、新たに空いた空間には0が挿入されます。
例として、1バイトの2進数で10進数の10を表現すると　　のように表現されるので、これを用いて説明を行います。

左シフト演算は (10 << N)　右シフト演算は(10 >> N)と書き、 N = 2をしてシフト演算します。
左シフト演算ではとなり + = です 10の4倍になりました。
右シフト演算はとなり、 = です。ビットの情報が失われ、2になってしまいます。

bit全探索では、主に1に対し左シフト演算を行いフラグを移動させていきます。

AND演算

AND演算はビット列の同じ位置のビットを比較し、互いに1の場合のみ1を返す演算子の一つです。
コードを書くときは & で示されます。

例として、10と8のAND演算を行う場合、10 & 8 = 8となります。

bit全探索では、シフトされた1とAND演算を行い、処理を行うかどうか判断します。

bit全探索の使用例

AtCoderで出題された過去問題のC - Train Ticketで使用例を見ていきます。

問題概要

4桁の数字ABCDが与えられる。A(op)B(op)C(op)D=7　が成立するように各(op)に"+"または"-"を入れ出力せよ。

考え方

演算子は3つかつ"+"と"-"の2通りしかないので、3ビットのbit全探索で探索可能であり、0の時に"+"を1の時に"-"の演算子を入れて計算する。

コード

#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i < (int)(n); i++)
using ll = long long;

using namespace std;
int main(){
	vector<int>Term(4);
	int num;
	cin >> num;
	rep(i, 4) {
		Term[3-i] = num % 10;
		num /= 10;
	}
	string ans = to_string(Term[0]);
	for (int tmp = 0; tmp < (1 << 3); tmp++) {	//演算子が入りうるすべての場所をbitで表現
		num = Term[0];
		rep(i, 3) {
			if (tmp & (4 >> i)) {
				num += Term[i+1] * (-1);
			}
			else {
				num += Term[i+1];
			}
		}
		if (num == 7) {
			rep(i, 3) {
				if (tmp & (4 >> i)) {
					ans += "-" + to_string(Term[i+1]);
				}
				else {
					ans += "+" + to_string(Term[i+1]);
				}
			}
			break;
		}
	}
	cout << ans << "=7" << endl;
}

コード解説

1. ABCDを分割して配列のTermに入れ、stringのansに式の一番最初の数を入れておきます。
2. for文を3bitで表現できる最大値まで繰り返し、その内部で0~2まで繰り返しを行います。
3. 内ループで4を右シフト演算し、tmpとAND演算を行い1なら"-"の処理、0なら"+"の処理を数字に行いnumに加算します。
4. numが7であれば、tmpから使用した演算子を読み取り、ansに数字と演算子を追加して出力します。

左シフト演算を主に使うと書いておきながら右シフト演算で探索しています。
この問題では1と0両方使う問題だった点、"+"と"-"の式では左から計算される点から右シフト演算で探索を行いました。
他にも値が大きいほうから取り出したい場合など右シフト演算を使うことがあります。

終わりに

APG4bの中のAC - 3.05.ビット演算を見て面白そうだなと思い練習問題に取り組みましたが、簡単な問題から水diffの問題まであり非常にためになったと思います。
水diffの問題とは知らず、他人のコードを参考にしながらやっとの思いで解いてAtCoder Problemsで確認したらびっくりしました。
これからも過去問や書籍などで勉強を重ね、様々な問題に対するアプローチを増やしていきたいです。