Goでbit演算

競プロでたまにbit全探索の問題に遭遇するけど、毎回どうやるんだっけってなってググっているのでまとめておく。

演算子について

&（AND）

「&（AND）」は2つのbitを比較してどちらも1なら1、どちらかが0の場合は0を返す。

例えば「100 & 101 = 100」

| （OR）

「|（OR）」は2つのbitを比較してどちらかが1なら1を返す。

例えば「100 | 101 = 101」

>> （右ビットシフト）

「>> （右ビットシフト）」はbitを右にずらす。意味的には2の-n乗することになる。

ずらしたことにより空いた部分には0が入り、桁数からはみ出た分は消す。このはみ出て消えることをオーバーフローと呼ぶ。

例えば「100 >> 1 = 010」

<< （左ビットシフト）

「<<（左ビットシフト）」はbitを左にずらす。意味的には2のn乗することになる。

例えば「101 << 1 = 1010」

package main

import "fmt"

func main() {
    var a uint = 4 // 100
    var b uint = 5 // 101

    fmt.Printf("10進数: %d, 2進数: %b\n", a&b, a&b)
    fmt.Printf("10進数: %d, 2進数: %b\n", a|b, a|b)

    fmt.Printf("10進数: %d, 2進数: %b\n", a>>1, a>>1)
    fmt.Printf("10進数: %d, 2進数: %b\n", b<<1, b<<1)
}

go.dev

Goでbit全探索

以下の基本的な問題をもとに考えていく。

atcoder.jp

N個の文字列について、選ぶor選ばないの2通りがあるので、2^N個のパターンがありこの全パターンを全探索したい。

全てのパターンをビットとして表したいので、0（全てを選ばないパターン）から2^Nまでのビットを考える必要がある。

よってfor文で0から1<<uint64(N)の1つ手前まで（範囲指定で<にすればOK）のパターンを考える。

各桁についてbitが1かどうかを考えれば良いので、bitsに対して0からNまでの数を右シフトして1かどうかを判定していく。 &1をしているのはその桁数が1かどうかを判定するため。

for bits := 0; bits < (1 << uint64(N)); bits++ {
    for i := 0; i < N; i++ {
        if (bits>>uint64(i))&1 == 1 {
            // 処理
        }
    }
}