ビット演算
ビット集合Gの全ての部分集合をイテレート
※φ以外
g = 0b11011010
h = g # hが求める数となる
while h:
print(f'{h:08b}')
h = (h - 1) & g
結果
11011010
11011000
11010010
11010000
11001010
11001000
11000010
11000000
10011010
10011000
10010010
10010000
10001010
10001000
10000010
10000000
01011010
01011000
01010010
01010000
01001010
01001000
01000010
01000000
00011010
00011000
00010010
00010000
00001010
00001000
00000010
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
結果
v:00011111 x:00000001 y:00100000 ~y:11011111 (v&~y):00011111 (v&~y)//x>>1:00001111
v:00101111 x:00000001 y:00110000 ~y:11001111 (v&~y):00001111 (v&~y)//x>>1:00000111
v:00110111 x:00000001 y:00111000 ~y:11000111 (v&~y):00000111 (v&~y)//x>>1:00000011
v:00111011 x:00000001 y:00111100 ~y:11000011 (v&~y):00000011 (v&~y)//x>>1:00000001
v:00111101 x:00000001 y:00111110 ~y:11000001 (v&~y):00000001 (v&~y)//x>>1:00000000
v:00111110 x:00000010 y:01000000 ~y:10111111 (v&~y):00111110 (v&~y)//x>>1:00001111
v:01001111 x:00000001 y:01010000 ~y:10101111 (v&~y):00001111 (v&~y)//x>>1:00000111
v:01010111 x:00000001 y:01011000 ~y:10100111 (v&~y):00000111 (v&~y)//x>>1:00000011
v:01011011 x:00000001 y:01011100 ~y:10100011 (v&~y):00000011 (v&~y)//x>>1:00000001
v:01011101 x:00000001 y:01011110 ~y:10100001 (v&~y):00000001 (v&~y)//x>>1:00000000
v:01011110 x:00000010 y:01100000 ~y:10011111 (v&~y):00011110 (v&~y)//x>>1:00000111
v:01100111 x:00000001 y:01101000 ~y:10010111 (v&~y):00000111 (v&~y)//x>>1:00000011
v:01101011 x:00000001 y:01101100 ~y:10010011 (v&~y):00000011 (v&~y)//x>>1:00000001
v:01101101 x:00000001 y:01101110 ~y:10010001 (v&~y):00000001 (v&~y)//x>>1:00000000
v:01101110 x:00000010 y:01110000 ~y:10001111 (v&~y):00001110 (v&~y)//x>>1:00000011
v:01110011 x:00000001 y:01110100 ~y:10001011 (v&~y):00000011 (v&~y)//x>>1:00000001
v:01110101 x:00000001 y:01110110 ~y:10001001 (v&~y):00000001 (v&~y)//x>>1:00000000
v:01110110 x:00000010 y:01111000 ~y:10000111 (v&~y):00000110 (v&~y)//x>>1:00000001
v:01111001 x:00000001 y:01111010 ~y:10000101 (v&~y):00000001 (v&~y)//x>>1:00000000
v:01111010 x:00000010 y:01111100 ~y:10000011 (v&~y):00000010 (v&~y)//x>>1:00000000
v:01111100 x:00000100 y:10000000 ~y:01111111 (v&~y):01111100 (v&~y)//x>>1:00001111
v:10001111 x:00000001 y:10010000 ~y:01101111 (v&~y):00001111 (v&~y)//x>>1:00000111
v:10010111 x:00000001 y:10011000 ~y:01100111 (v&~y):00000111 (v&~y)//x>>1:00000011
v:10011011 x:00000001 y:10011100 ~y:01100011 (v&~y):00000011 (v&~y)//x>>1:00000001
v:10011101 x:00000001 y:10011110 ~y:01100001 (v&~y):00000001 (v&~y)//x>>1:00000000
v:10011110 x:00000010 y:10100000 ~y:01011111 (v&~y):00011110 (v&~y)//x>>1:00000111
v:10100111 x:00000001 y:10101000 ~y:01010111 (v&~y):00000111 (v&~y)//x>>1:00000011
v:10101011 x:00000001 y:10101100 ~y:01010011 (v&~y):00000011 (v&~y)//x>>1:00000001
v:10101101 x:00000001 y:10101110 ~y:01010001 (v&~y):00000001 (v&~y)//x>>1:00000000
v:10101110 x:00000010 y:10110000 ~y:01001111 (v&~y):00001110 (v&~y)//x>>1:00000011
v:10110011 x:00000001 y:10110100 ~y:01001011 (v&~y):00000011 (v&~y)//x>>1:00000001
v:10110101 x:00000001 y:10110110 ~y:01001001 (v&~y):00000001 (v&~y)//x>>1:00000000
v:10110110 x:00000010 y:10111000 ~y:01000111 (v&~y):00000110 (v&~y)//x>>1:00000001
v:10111001 x:00000001 y:10111010 ~y:01000101 (v&~y):00000001 (v&~y)//x>>1:00000000
v:10111010 x:00000010 y:10111100 ~y:01000011 (v&~y):00000010 (v&~y)//x>>1:00000000
v:10111100 x:00000100 y:11000000 ~y:00111111 (v&~y):00111100 (v&~y)//x>>1:00000111
v:11000111 x:00000001 y:11001000 ~y:00110111 (v&~y):00000111 (v&~y)//x>>1:00000011
v:11001011 x:00000001 y:11001100 ~y:00110011 (v&~y):00000011 (v&~y)//x>>1:00000001
v:11001101 x:00000001 y:11001110 ~y:00110001 (v&~y):00000001 (v&~y)//x>>1:00000000
v:11001110 x:00000010 y:11010000 ~y:00101111 (v&~y):00001110 (v&~y)//x>>1:00000011
v:11010011 x:00000001 y:11010100 ~y:00101011 (v&~y):00000011 (v&~y)//x>>1:00000001
v:11010101 x:00000001 y:11010110 ~y:00101001 (v&~y):00000001 (v&~y)//x>>1:00000000
v:11010110 x:00000010 y:11011000 ~y:00100111 (v&~y):00000110 (v&~y)//x>>1:00000001
v:11011001 x:00000001 y:11011010 ~y:00100101 (v&~y):00000001 (v&~y)//x>>1:00000000
v:11011010 x:00000010 y:11011100 ~y:00100011 (v&~y):00000010 (v&~y)//x>>1:00000000
v:11011100 x:00000100 y:11100000 ~y:00011111 (v&~y):00011100 (v&~y)//x>>1:00000011
v:11100011 x:00000001 y:11100100 ~y:00011011 (v&~y):00000011 (v&~y)//x>>1:00000001
v:11100101 x:00000001 y:11100110 ~y:00011001 (v&~y):00000001 (v&~y)//x>>1:00000000
v:11100110 x:00000010 y:11101000 ~y:00010111 (v&~y):00000110 (v&~y)//x>>1:00000001
v:11101001 x:00000001 y:11101010 ~y:00010101 (v&~y):00000001 (v&~y)//x>>1:00000000
v:11101010 x:00000010 y:11101100 ~y:00010011 (v&~y):00000010 (v&~y)//x>>1:00000000
v:11101100 x:00000100 y:11110000 ~y:00001111 (v&~y):00001100 (v&~y)//x>>1:00000001
v:11110001 x:00000001 y:11110010 ~y:00001101 (v&~y):00000001 (v&~y)//x>>1:00000000
v:11110010 x:00000010 y:11110100 ~y:00001011 (v&~y):00000010 (v&~y)//x>>1:00000000
v:11110100 x:00000100 y:11111000 ~y:00000111 (v&~y):00000100 (v&~y)//x>>1:00000000
v:11111000 x:00001000 y:100000000 ~y:11111111 (v&~y):11111000 (v&~y)//x>>1:00001111
bitが立っている条件の言い換え
正整数 $X$ で、$2^d$ の位のbitが立っているかの判定は、当然「$X \& 2^d$」でできる。
だが、$X$ を様々に変えて判定したいときなど、別の表現ができると嬉しいことがある。
特に3番目は、複数の $X$ で、$2^d$ が立っている数が何個あるかを求めたい場合、
引く方と引かれる方をそれぞれまとめて計算してから合計同士を引いても正しく求まるので、たまに使えることがある。