Processing math: 100%

−目次

ビット演算

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

※φ以外

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

結果

空集合（h=0）の時も処理をしたい場合は以下。

1
2
3
4
5
6
7
g = 0b11011010
h = g  # hが求める数となる
while True:
    print(f'{h:08b}')  # 何らかの処理
    if h == 0:
        break
    h = (h - 1) & g

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

1
2
3
4
5
6
7
8
9
10
11
12
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の左右反転

まとまり毎に一気に動かすと、桁を k として log2k 回の移動で完了する。

下記の実装例は、64bitでの反転をおこなっておいて、最後にbitshiftすることで k 桁で反転した結果に変換できる。

途中で64bit符号付き整数の範囲を超えるため、多倍長精度への変換などで速度に影響しないかな？と思い、 32bitを上限としたものと比較したが、（32bitは計算が1回減るので5/6になるのは当然だが、それ以上の）差はほぼ見られなかった。

1
2
3
4
5
6
7
8
9
10
def bit_reverse64(n, k=64):
    """ k 桁の2進数の左右を反転する（k <= 64） """
    n = (n & 0xffffffff00000000) >> 32 | (n & 0x00000000ffffffff) << 32
    n = (n & 0xffff0000ffff0000) >> 16 | (n & 0x0000ffff0000ffff) << 16
    n = (n & 0xff00ff00ff00ff00) >> 8 | (n & 0x00ff00ff00ff00ff) << 8
    n = (n & 0xf0f0f0f0f0f0f0f0) >> 4 | (n & 0x0f0f0f0f0f0f0f0f) << 4
    n = (n & 0xcccccccccccccccc) >> 2 | (n & 0x3333333333333333) << 2
    n = (n & 0xaaaaaaaaaaaaaaaa) >> 1 | (n & 0x5555555555555555) << 1
    n >>= 64 - k
    return n

bitが立っている条件の言い換え

正整数 X で、2d の位のbitが立っているかの判定は、当然「X&2d」でできる。

だが、X を様々に変えて判定したいときなど、別の表現ができると嬉しいことがある。

特に3番目は、複数の X で、2d が立っている数が何個あるかを求めたい場合、 引く方と引かれる方をそれぞれまとめて計算してから合計同士を引いても正しく求まるので、たまに使えることがある。