bit全探索

NOTE#001

背景

AtCoderでの解法としてのメモ(abc374_c)

実装

配列からすべての組み合わせを探索するなどで使用。

2のx乗

1 << x

AND演算

2つの値に対して対応するbitを比較し、両方のbitが1である場合にだけ1になる演算。

ビットA	ビットB	結果（A & B）
0	0	0
0	1	0
1	0	0
1	1	1

例: 12 & 7

• 12は2進数で1100。
• 7は2進数で0111。
• 結果は0100。つまり十進数で4。

AND演算の使い方

AND演算はbit操作において多く使われている。その代表的な使い方。

特定のビットを確認する

i & (1 << j)のようにして、整数iのj番目のビットが 1 かどうか確認。

実装例

もとの配列から2つの配列グループに分ける。
その全パターン探索用の処理実装。

let mut cnt = 0;
let arr_len = 5;
for i in 0..(1 << arr_len) {
    cnt += 1;
    println!("cnt: {}", cnt);
    for j in 0..arr_len {
        if i & (1 << j) != 0 {
            println!("true");
        } else {
            println!("false")
        }
    }
}