Rubyで競技プログラミング bit演算の基礎まとめ

はじめに

最近、競技プログラミングの勉強をはじめました。仕事で求められるものとはまた違った知識・経験が要求され、なかなか難しさを感じています。
この記事では競技プログラミングを通して学んだ、Rubyを用いたbit演算の基礎をまとめたいと思います。

bit演算の基礎

表示

0b を先頭につけることで2進数表示にできます。

irb(main):> bit = 0b101
irb(main):> bit
=> 5

論理回路

& は積(AND)、| は和(OR)、~は否定(NOT)、 ^ は排他的論理和(XOR)を示します。

irb(main):> bit = 0b101 # 10進数では5
irb(main):> another_bit = 0b111 # 10進数では7
irb(main):> bit & another_bit
=> 5 # 0b101
irb(main):> bit | another_bit
=> 7 # 0b111
irb(main):> ~bit
=> -6 # 0b..1010 # 右3桁が010の反転bit
irb(main):> bit ^ another_bit
=> 2 # 0b010

シフト演算

>> で右論理シフト、 << で左論理シフトです。右論理シフトは1/2ⁿ倍され、左論理シフトは2ⁿ倍されます。

irb(main):> bit = 0b101 # 10進数では5
irb(main):> bit >> 1 # 余りは切り捨て
=> 2 # 0b010
irb(main):> bit << 1
=> 10 # 0b1010

フラグ管理

フラグを立てるときは | を、フラグを下ろすときは ~ と & を使います。

# フラグを立てる
irb(main):> bit = 0b000
irb(main):> bit
=> 0
irb(main):> bit >> 0 | 1
=> 1
irb(main):> bit >> 1 | 1
=> 1
irb(main):> bit >> 2 | 1
=> 1
# フラグを下ろす
irb(main):> another_bit = 0b111
irb(main):> ~another_bit >> 0 & 1
=> 0
irb(main):> ~another_bit >> 1 & 1
=> 0
irb(main):> ~another_bit >> 2 & 1
=> 0

フラグの有無

先程の右論理シフトを使うことで、右からそれぞれの桁の値を見ることができます。
またフラグの有無を調べるとき気をつけることは、Rubyは0, 1どちらもtrue判定になるので、必ず1かどうか確認する必要があります。

irb(main):> bit = 0b101
irb(main):> bit >> 0 & 1
=> 1 # 0番目は1なので 1 & 1
irb(main):> bit >> 1 & 1
=> 0 # 1番目は0なので 0 & 1
irb(main):> bit >> 2 & 1
=> 1 # 2番目は1なので 1 & 1
irb(main):> bit >> 0 & 1 == 1
=> true # 1だったらtrue, 0ならfalse

bit全探索

最後にbit全探索です。
下のコードを説明すると、 1<<3 は計算量O(2ⁿ) より 2³ となるので、 8回繰り返すことになります。0 <= i <= 7をprintf("%03b\n", i) で2進数表記にして表示しています。
こうすることで、フラグ有無の全組み合わせを試すことができるようになります。

irb(main):115:0> (1 << 3).times { |i| printf("%03b\n", i) }
000
001
010
011
100
101
110
111

おわりに

bit全探索は頻出問題ですが、ちゃんと勉強しないと取っ付きにくい分野だと思いました。 ただ、解き方に慣れればあとはただの全探索なので、競技プログラミングの最初の壁といった感覚ですね。
次はDPの慣れを増やしていきたい。