[[ビット演算]]
現在位置: トップページ » アルゴリズム » ビット演算
管理サイトマップ

目次

ビット演算

ビット集合Gの全ての部分集合をイテレート

※φ以外 

g = 0b11011010
h = g  # hが求める数となる
while h:
    print(f'{h:08b}')
    h = (h - 1) & g

結果

N個の内、K個のビットが立った数をイテレート

n = 8
k = 5
LIMIT = 1 << n

v = (1 << k) - 1  # ここからスタート(vが求める数となる)

while v < LIMIT:
    x = v & -v
    y = v + x
    print(f'v:{v:08b}  x:{x:08b}  y:{y:08b}  ~y:{bin(~y + (1 << 32))[-8:]}'
          f'  (v&~y):{(v & ~y):08b}  (v&~y)//x>>1:{(v & ~y) // x >> 1:08b}')
    v = (v & ~y) // x >> 1 | y

結果

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$ が立っている数が何個あるかを求めたい場合、 引く方と引かれる方をそれぞれまとめて計算してから合計同士を引いても正しく求まるので、たまに使えることがある。

programming_algorithm/bit_operation.txt · 最終更新: 2023/09/01 by ikatakos
メディアマネージャー文書の先頭へ
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0