初めてのビット操作を使った全探索
問題 (AtCoder ABC002 D)
ソースコード
解説
ビット操作により全探索をする。この問題はNの数が最大でも12なので、最大でも212 = 4096通り。 候補に対して、その要素を含むか否かの2パターンを12要素分行う。 その際、その要素を含むか否かをビットを用いて管理する。 含む=> 1 含まない=> 0
例 N = 4の時、N桁の2進数で管理「0000」。 0001: 一つ目の要素が含まれる 0100: 3つ目の要素が含まれる 0101: 1つ目と3つ目の要素が含まれる
ポイント1
要素を含むか否かを全列挙するためにビット操作
for (int i = 0; i < 1<<N; i++) { //.... }
このループで全てのパターンを列挙できる。
1<<N
について
<<
演算子は指定した数値の数だけ左にシフトするというもの。
つまり、N = 3 のとき、1<<N
は1<<3
となり、1000となる。
この時、i < 1000 → iが111まで繰り返すことになる。(2進数だから1000の1つ前は111)
これより、このループでは全てのパターンを列挙することができる。
ループ中のiの動き
0 1 10 11 100 101 110 111 1000
ポイント2
if ((1 & i >> j) == 1) {
について これは、2進数のそれぞれの桁数を見てあげて、その要素が1であればリストに追加するという処理。
例
i = 101の時 j = 0 (シフト無し) ``1 & i >> j`` → `` 1 & 101`` (1& は一桁目を見るから) → 1 j = 1 (1つ右にシフト) ``1 & i >> j`` → `` 1 & 10`` (1& は一桁目を見るから) → 0 j = 2 (2つ右にシフト) ``1 & i >> j`` → `` 1 & 1`` (1& は一桁目を見るから) → 1
コレによってiの中でフラグが立っている要素のみ、リストに加える事ができる。