杂-整数的二进制中有几个1

x & (x - 1) 消除x最后一位的1

x = 15
    15 = 0b1111
    14 = 0b1110
y = x & (x-1)
y = 0b1110  # 消去了x最后一位的1

y = 14
    14 = 0b1110
    13 = 0b1101
z = y & (y-1)
z = 0b1100  # 消去了y最后一位的1
……

• O(1) 时间检测X是否是2的n次方

  一个数如果是2的n次方，则这个数的二进制中只有一个1
  如果消去最后一位的1，则这个数为0

  x = 16
    16 = 0b10000
    15 = 0b01111
  x & (x - 1) = 0

• 一个整数的二进制中有多少个1

  x & (x - 1) 可以消除最后一位的1
  while循环消除最后一位的1，直到结果为0

  a = 15
  b = 0
  while a > 0:
    a = a & (a - 1)
    b += 1
  print b # 1的个数