🦔
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")
}
}
}
Discussion