🦔

bit全探索

2024/10/12に公開

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)のようにして、整数ij番目のビットが 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