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/2n倍され、左論理シフトは2n倍されます。
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(2n) より 23 となるので、 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の慣れを増やしていきたい。