はじめに
ビットの扱いが不慣れでビット全探索をするときは毎回コピペすることでやり過ごしていました。しかし、以下の記事で水色コーダーになるためにはbitsetやビット全探索は知っておきたいと紹介されていたので、この機会にちゃんと理解しようと思いました。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】
今回の記事の内容は自分が詰まっていたところです。ビット演算に関しては以下の記事が詳しいです。
ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜
詰まっていたところ
全ての元凶はシフト演算子>>でした。シフト演算子はビットを左右にずらすものだと思っていました(その通りなんですが)。例えば、
for (int bits = 0; bits < (1 << n); bits ++)
ビット全探索では上のような部分をよく見かけます。このとき、「(1 << n)の部分は1のビットをn桁左にずらすだけなのに、なぜこれが終了条件になるの？」と疑問に思っていました(この疑問わかってもらえますか？)。しかし実際は「数値１を２進数で表したものをn桁左シフトしたものの値」だったんですね。
実際に手元で試してみると、
cout << (1 << 5) << endl; // 32
cout << (1 << 10) << endl; // 1024
と値が返ってきています。どうやらシフトするという処理とその結果を混同していたようです。
さらに詰まっていたところ
シフト演算子の左右の位置って重要なんですね。いつも左側が1だったので順番を意識していませんでした。x << yならxの２進数表現の値をy桁分左にシフト、x >> yならxの２進数表現の値をy桁分右にシフトとなるんですね。目が開かれる思いでした。
いざビット全探索！
では、ビット全探索でよく出てくる部分を読み解いていきます。まずはこちら。
for (int bits = 0; bits < (1 << 5); bits ++)
bits < (1 << 5)の部分は1(0b000001)を５桁分左シフトしたもの(0b100000)なので32を終了条件とするということですね。仕組みがわかれば楽チンです。
次はこちら。
if (bits & (1 << 5))
// bits == 33 (0b100001)のとき
if (0b100001 & (0b100000)) // -> if (0b100000) -> if (32) -> true
// bits == 31 (0b011111)のとき
if (0b011111 & (0b100000)) // -> if (0b000000) -> if (0) -> false
分解すれば上のようになり、このif文も理解できました。bits & (1 << n)でやりたいことは、bitsのn桁目のフラグが立っているかどうかのチェックとなります。1 << nのフラグはn桁目の１つしか立っておらず、それとの論理積で0が返ってきた時は、bitのn桁目のフラグが立っていないことになるというわけですね。
おわり
書いてて思ったんですが、２進数のまま考えた方が分かりやすい気がしましたし、その方がビット全探索でやりたいことにも適していると思います。ビット演算子に慣れないために２進数の世界と１０進数の世界を行ったり来たりして頭がこんがらがっていました。今後はビット演算子を使うときは２進数の世界に常駐していようと思います。
編集履歴
2020/03/03 22:08
0から始まるリテラルは８進数とのご指摘を受け、２進数であることを明確にするためリテラル0bを追記しました。
2020/03/03 22:12
bitを複数形のbitsに修正しました。