Bit全探索のおはなし
はじめに
この記事はKogakuin Univ Advent Calendar 2019 - Adventarの18日目の記事です。
お久しぶりです。今までの記事を全てみてくださった方には今年三回目のご挨拶となりますね。
突然ですが、朗報があります。なんと！アドベントカレンダーが全枠埋まりました！！！！！！！
ありがとうございます。特に複数記事を書かせた書いてくれた方々、卒業しても書いてくださった方々には感謝してもしきれません。
というわけでお待たせしました。bit全探索のおはなしに入ろうと思います。
Bitとは
とりあえず基礎から入っていきましょう。完全に理解している方はスルーしてください。
ビットとは、情報量の最小単位で、二つの選択肢から一つを特定する情報の量。語源は “binary digit” （二進法の数字）と言われ、コンピュータなどでは0と1のいずれかを取る二進数の一桁として表される。
わかりやすいですね。とりあえず、情報を「0」と「1」の2つの状態で表すんだな〜と覚えていただければOKです。
二進数とは
次は二進数についてです。
2進数とは、数を書き表す方法（記数法）の一つで、基数を2（二）とした表記法のこと。通常、アラビア数字の「0」と「1」の二つの数字を用いてすべての数を表現する。2進数の値の連なりとして表現されたデータ形式を「バイナリ」（binary）という。
二進数は、数を「0」と「1」のみで表現するやつと覚えていただければOKです。
では、少し練習してみましょう！
問題1：10進数表記で「10」を二進数表記にすると
A：1010問題2：10進数表記で「64」を二進数表記にすると
A：1000000問題3：10進数表記で「1023」を二進数表記にすると
A：1111111111
分からなかった方はネットワークの勉強をはじめから - 2進数と10進数の変換方法を見るといいと思います。
Bit全探索の考え方
お待たせしました。本題に入ります。
まず、Bit全探索の考え方について 簡単に言うと「ON/OFF」「True/False」「Yes/No」などの2つの事象で全てを表すことができるものの全ての組み合わせを列挙する際に強力な武器となる考え方です。
この考え方は、bitの「0」をとある事象に対する「False」、「1」を「True」として、全ての「True」と「False」の組み合わせを試していくものとなります(ただの概念だから、逆にしても実装はできるよ)。 時間計算量は少なくともO(2n)はかかるため、nが小さいときのみ有効な手法となります。
分かりにくいので例を出します。
4人の大人または子供を一列に並べる。このとき、子供を「0」大人を「1」とすると重複しない全ての並べ方は、 「0000」「0001」〜「1110」「1111」までの16種類の「0」と「1」のみの列で表現することができます。
この画像の10進数表記に疑問を持った方もいらっしゃるでしょう。 ここで先程例に挙げた並べ方のBit列を十進数にしてみると、0〜15の連続した16種の数字であることが分かります。
で？どうやって実装すればいいの？
実装では「連続した数字で全ての組み合わせを表現できる」が大事な考え方となってきます。
実装例を見てみよう！
以下のコードは「000」~「111」までを表示するプログラムとなっています。 先程説明したように「000」~「111」までのBit列は10進数として考えることができます。そのため、0から7まで1づつ増やし、その都度数字を10進数から2進数に変換することで比較的簡単に実装することができます。
このコードの初見殺しの部分を補足します。
まずは「1LL << i」。 1LLはlong long型の1という意味です。
「<<」はシフト演算です。以下の画像を見れば分かると思います。
編集の都合上で何進数かを示す(2)や(10)を省略していますので、エスパーで感じ取ってください。
次に「bit & (1LL << i)」 「&」はAND演算。論理回路で学んだ方も多いと思います。 知らない方はhttp://www.cs.shinshu-u.ac.jp/Lecture/LogicCirc/chap7/chap7.htmlへGO!
さて、この演算何をやっていると思いますか？
ここから、bitに代入された数を2進数として見たときの下からi番目(0スタート)のBitが立っている、つまり1であるかどうかを知ることができると分かります。 また、C言語(C++)のif文では、条件式の値が0だと「False」0以外だと「True」になることを利用し、「if( bit & (1LL << i) )」が真のときにはBitが立っており、偽のときにはBitが立っていないと判断することができます。
演習
いい演習問題がAtCoderにあったため紹介します。
atcoder.jp
私の実装例
この問題が解けた方は atcoder.jp
を解いてみてください。私の実装例
さいごに
閲覧いただきありがとうございました。 大遅刻してしまって本当に申し訳ございません。
Bit全探索の考え方はプログラミングで役に立ちます。 ぜひこの記事を見てくださったプログラマーの方は覚えて帰ってください！
ではまた次回どこかでお会いしましょう。 ありがとうございました！
