运算技巧

乘2

a * 2 == a << 1，正负通用

-1024 = 0b11111111111111111111110000000000
-2048 = 0b11111111111111111111100000000000

乘2加1

a * 2 + 1 == a << 1 | 1，正负通用

-1024 = 0b11111111111111111111110000000000
-1023 = 0b11111111111111111111110000000001

除2

a / 2 == a >> 1，不能整除时向下取整

取相反数

~a + 1，补码表示法

  1024 = 0b00000000000000000000010000000000
 -1024 = 0b11111111111111111111110000000000
 ~1024 = 0b11111111111111111111101111111111
~-1024 = 0b00000000000000000000001111111111

消去最低位1

a & (a - 1)

0b00010110 -1 = 0b00010101

0b00011000 -1 = 0b00010111

0b11111000(-8) -1 = 0b11110111(-9)

获取最低位1

a & (-a) = a & (~a + 1)

 22 = 0b00010110
~22 = 0b11101001
 +1 = 0b11101010(-22)
 &  = 0b00000010

判断

判断奇偶

a & 1

判断是否是2的幂次方

a & (a - 1) == 0

二进制枚举子集

n = 0b1011
sub = n
while sub:
    print(bin(sub))
    sub = (sub - 1) & n
0b1011
0b1010
0b1001
0b1000
0b11
0b10
0b1

二进制连续1的个数

n = 0b11101111
ans = 0
while n:
  	ans += 1
		print(bin(n))
		n = n & n >> 1
    
0b11101111
0b1100111
0b100011
0b1