bit全探索について - xyoshixaki’s diary

競技プログラミングをやっていて、bit全探索というものを始めて聞いて、「ふぁ？」ってなったので、自己理解のためにまとめてしました。

bit全探索とは二進数とbitを用いて、全探索すること！

うむ、分からんw

取り敢えず分解してみましょ

bitというと、0と1だけで数字を表現すること。

普段だと0～9という10個の数字で表現する10進数を使っていますが、そうではなく、0と1だけであらわします。10進数を2進数に直すとこんな感じ♪

例）2 -> 10

3 -> 11

4 -> 100

6 -> 110

8 -> 1000

全探索とは全ての組み合わせを調べてあげる方法のことです（7割理解なので、厳密には違うかも）

例えば、a,b,cの3つの組み合わせを全部調べるなら、

「何もなし」「aのみ」「bのみ」「cのみ」「aとb」「bとc」「cとa」「aとbとc」

の8通り。2の3乗=8が組み合わせの数になります。

この8通りに対して、処理を実施するのが全探索です。

参考にした記事がこちらです

つまり、

bit全探索とは

bit形式（二進数）にして、全ての組み合わせを調べること、らしいです

使用するメリットはきちんと書いている記事が見つからなかったので、何とも言えないのですが、1問解いて感じたのは、処理を簡潔にできる。

bit形式で表記するのは、複数のtrue・falseを管理したい場合っぽいです。（有名なところだと、linuxのファイルパーミッション）

そういった複数のtrue・falseを網羅して、プログラムを書く時にそのまま書くと、1個1個条件分岐を書かないといけなくなってしまう。

すると、ネストがめちゃくちゃ深くなるし、ソースも複雑になってしまう。

ということで、処理を簡潔に書くために、bit形式にして複数のtrue・falseを一括管理してしまおうということがbit全探索を使用する目的っぽい感じがしました。

javaを扱ったことがある人ならわかると思うけど、intクラスをただ使うだけじゃ、bit方式で計算してくれません(＞＜)

数字をbit全探索するには下の感じにする必要があります

		for (int i=0; i<(1<<n); i++) {
			//ループ処理
		}

通常のfor文と違う点は2つ目のループ処理を抜けるための条件。

「(1<<n)」でbit形式として処理されるようです。

ループ回数は2のn乗回実行する、という意味です。

n=3の時だと2の3乗になるので、8回ループするということになります。

今回はbit全探索の解説をしました。

何か、追加で分かったことがあったら、追記します。

※本記事は筆者の自己理解を整理するために作成しています。

　頭悪いので、間違った解釈をしている可能性があるので、そこは温かく見守って頂けると嬉しいです。