差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| programming_algorithm:bit_operation [2019/02/13] – ikatakos | programming_algorithm:bit_operation [2023/09/01] (現在) – [bitが立っている条件の言い換え] ikatakos | ||
|---|---|---|---|
| 行 130: | 行 130: | ||
| </ | </ | ||
| ++++ | ++++ | ||
| + | |||
| + | |||
| + | ===== bitが立っている条件の言い換え ===== | ||
| + | |||
| + | 正整数 $X$ で、$2^d$ の位のbitが立っているかの判定は、当然「$X \& 2^d$」でできる。 | ||
| + | |||
| + | だが、$X$ を様々に変えて判定したいときなど、別の表現ができると嬉しいことがある。 | ||
| + | |||
| + | * $X$ で $2^d$ のbitが立っている | ||
| + | * $X$ を $2^{d+1}$ で割ったあまりが、$2^d$ 以上 | ||
| + | * $\left \lfloor \dfrac{X+2^d}{2^{d+1}} \right \rfloor - \left \lfloor \dfrac{X}{2^{d+1}} \right \rfloor = 1$ | ||
| + | |||
| + | 特に3番目は、複数の $X$ で、$2^d$ が立っている数が何個あるかを求めたい場合、 | ||
| + | 引く方と引かれる方をそれぞれまとめて計算してから合計同士を引いても正しく求まるので、たまに使えることがある。 | ||
| + | |||
