考察典型 : bit 演算 → 2 進数の桁ごとに考える

超天啓になりがち。

概要

bitwise XOR を始めとした bit 演算には、

$ 2進数における桁ごとに分割して答えを計算

最後に全ての桁を纏め上げる

というように答えを計算できるという特徴がある。

実例

bitwise XOR 演算を$ \oplusとする。

$ 5 \oplus 9 \oplus 11を計算したい。このとき、これらを$ 2進数に変換すると、それぞれ

code:txt

0101

1001

1011

となる。

桁ごとに$ 1が出現する回数を数えて$ 2で割ったあまりを取ると、0111となる。(これは既に全ての桁が纏め上げられた状態になっている)

そして、実際に$ 5 \oplus 9 \oplus 11 = 7となる。

応用

bitwise XOR

「繰り上がりのない加算」と考えることが出来る。そのため、$ x + y \geq x \oplus yが成り立つ。

bitwise OR

一度$ 1になった bit は$ 0にならない。そのため、選んだ要素の bitwise OR が$ Xを超えないように、選ぶ集合の大きさや実際に bitwise OR をした値を最大化するなどの問題が考えられる。

bitwise AND

答えの$ ibit 目を立てるのに、bitwise AND する対象の値について全て$ ibit 目が$ 1である必要がある。

逆の場合は$ 1つ以上$ ibit 目が$ 0である値が存在しなくてはならない。

この考察典型を用いる問題