今日は全校出校日で、私も久々の出勤でした。
お盆明けの出勤はやはり疲れるものがあります。
何といって取り立ててやってもないし、
授業もしていないのだけれど…。
さて、今日はbit全探索の勉強をしました。
この記事を参考に勉強。
https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361
取り敢えずbitとはなにか、というところで
整数を二進法で表したときに1と0の並びになる…その時何番目に1があるか、というその番号の集合がbitらしい？
そしてbit演算とは、
AND & の場合（左2つを照らし合わせて右列が出力）
0 0 0
0 1 0
1 0 0
1 1 1
OR | の場合
0 0 0
0 1 1
1 0 1
1 1 1
と、二進法で表された数字同士を各桁で照らし合わせ、演算するものを指すそうです。
そして、ビットシフト演算子なるものがあり、
bit に i 番目のフラグが立っているかどうかは if ((bit>>i) & 1) と表記します。
やっと本題。
bit 全探索とは、n個の要素からなる集合 {0,1,…,n−1} の部分集合をすべて調べ上げる手法のことです。
for (int bit = 0; bit < (1<<n); ++bit){ bitで表される集合の処理 }
という形で実施することができます。
これは、「右からn番目に1というフラグが立っている状態の手前までbitという整数を0から始めて列挙せよ」という意味（で合ってるのかな…？）なので
n番目に1、つまり100000000…000（n個分の0）の一個手前、よって
11111111…1111（n個分の1）まで全て列挙していくことを指示しています。
だから、例えばn=3なら
1000まで、
0000 {}
0001 {0}
0010 {1}
0011 {0,1}
0100 {2}
0101 {0,2}
0110 {1,2}
0111 {0,1,2}
という風に全ての状態を洗い出すことができる！
これがbit全探索なんですね。
ということでこの問題を解きました。
これはもう優秀な人のソースコードを見て真似して書いてみて、理解することの方に尽力しようとしたのですが
sumにどうして毎回-'0'が付くのか分からない…。
ここは理解できるように課題だなぁ。
取り敢えず実装してみて慣れるのみ、という感じがします。
明日から2日間また遠くでお仕事です。
頑張らなきゃ…
