ビット演算の読み替え
概要
ビット演算全般について、下記のようにそれぞれ「ビットごとに〇〇する演算」と言い換えることができる。
- AND : min, mod2 での積
- OR : max
- XOR : mod2 での和
- NOT : mod2 での +1
利用方法
詳しくは参考リンクを参照すること。
非負整数 \(a, s\) が与えられたとき下記のような \(x, y\) が存在するかどうかを考える。
- \(x \hspace{2mm} AND \hspace{2mm} y = a\)
- \(x+y=s\)
この時ビット演算の読み替えを利用すると
\[\begin{split}
x + y &= \textrm{min}(x, y) + \textrm{max}(x, y) \\&= (x \hspace{2mm}AND\hspace{2mm}y) + (x\hspace{2mm}OR\hspace{2mm}y)
\end{split}\]
が成り立つことから \(a \leq s\)の時
- \(x \hspace{2mm} AND \hspace{2mm} y = a\)
- \(x \hspace{2mm} OR \hspace{2mm} y = s - a\)
のように変形することができる。この時\(x \leq y\)と仮定すると以下のようになり、\(a\hspace{2mm}AND\hspace{2mm}(s-a)=a\)のように\(a, s\)を使った判定に帰結することができる。
- \(x=a\)
- \(y=s-a\)
- \(a\hspace{2mm}AND\hspace{2mm}(s-a)=a\)