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

算法
发布日期:   2021-03-07
文章字数:   175
阅读时长:   1 分

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

1
2
3
4
5
6
7
8
9
10
11
12
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

    1
    2
    3
    4
    x = 16
    	16 = 0b10000
    	15 = 0b01111
    x & (x - 1) = 0
  • 一个整数的二进制中有多少个1

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

    1
    2
    3
    4
    5
    6
    a = 15
    b = 0
    while a > 0:
    	a = a & (a - 1)
    	b += 1
    print b # 1的个数
算法
  目录