ビット演算

読了目安 約3分

2 進数の桁を直接操作する。集合をビットで表し、bit 全探索で選び方を全列挙する。

コンピュータの中で、整数は 2 進数 (0 と 1 の並び) で表されています。 その桁を直接操作するのがビット演算です。 競プロでは「選ぶ・選ばない」の全パターン列挙に威力を発揮します。

2 進数リテラル

数値の先頭に 0b を付けると 2 進数で書けます。 String(x, radix: 2) で 2 進数の文字列に戻せます。

let x = 0b1010
print(x)
print(String(x, radix: 2))

ビット演算子

let a = 0b1100
let b = 0b1010
print(String(a & b, radix: 2))
print(String(a | b, radix: 2))
print(String(a ^ b, radix: 2))
print(a << 1, a >> 2)

<< 1 は 2 倍、>> 1 は 2 で割った商と同じです。

~ は符号のビットも反転するため、Int では結果が負になります。 実際の出番は、後述の「特定のビットを消す」形がほとんどです。

集合をビットで表す

n 個の要素それぞれの「入っている・いない」は、n ビットの整数 1 個で表せます。 i 番目の要素をビット 1 << i に対応させます。 この使い方はフラグ管理とも呼ばれます。

var bits = 0
bits |= 1 << 0
bits |= 1 << 2
print(String(bits, radix: 2))
print(bits & (1 << 2) != 0)
print(bits & (1 << 1) != 0)

bit 全探索

0 から 2^n − 1 までの整数は、n 個からの選び方すべてと 1 対 1 に対応します。 つまり、整数のループを回すだけで全パターンを列挙できます。 この手法を bit 全探索と呼びます。

let n = 3
for bits in 0..<(1 << n) {
    var subset: [Int] = []
    for i in 0..<n {
        if bits & (1 << i) != 0 {
            subset.append(i)
        }
    }
    print(bits, subset)
}

試してみよう: n を 4 に変えて、16 通りが列挙されることを確かめてください。

外側が 2^n 回、内側が n 回なので、計算量は O(2^n × n) です。 n が 20 くらいまでの「選ぶ・選ばない」問題なら、この型で全部調べられます。

学びどころ

演習

1 行目に整数 N と X が空白区切りで入力されます。 2 行目に N 個の整数 v_1 … v_N が空白区切りで入力されます。

N 個から何個か選んで (1 個も選ばなくてもよい)、合計をちょうど X にできるなら Yes、できなければ No を出力してください。

制約: 1 ≤ N ≤ 10、1 ≤ v_i ≤ 1000、0 ≤ X ≤ 10000

入力例:
3 7
2 3 5

出力例:
Yes

2 と 5 を選ぶと合計 7 になります。

let first = readLine()!.split(separator: " ").map { Int($0)! }
let n = first[0]
let x = first[1]
let v = readLine()!.split(separator: " ").map { Int($0)! }

var found = false
for bits in 0..<(1 << n) {
    var sum = 0
    for i in 0..<n {
        if bits & (1 << i) != 0 {
            sum += v[i]
        }
    }
    if sum == x {
        found = true
    }
}

if found {
    print("Yes")
} else {
    print("No")
}