差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:bit_operation [2019/02/13] – ikatakos | programming_algorithm:bit_operation [2023/09/01] – ikatakos | ||
|---|---|---|---|
| 行 3: | 行 3: | ||
| * [[https:// | * [[https:// | ||
| * [[https:// | * [[https:// | ||
| + | * [[https:// | ||
| =====ビット集合Gの全ての部分集合をイテレート===== | =====ビット集合Gの全ての部分集合をイテレート===== | ||
| 行 129: | 行 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$ での結果の合計を求めたい場合、 | ||
| + | 引く方と引かれる方をそれぞれまとめて計算してから合計同士を引いても正しく求まるので、たまに使えることがある。 | ||
| + | |||
