摄影：产品经理买单：kingname
任意给出一个正整数，例如4523，如何快速统计它的二进制值里面有几个1？
我们知道，在 Python 里面，查看一个数字的二进制函数为：bin，例如：
>>> bin(4523) '0b1000110101011'
所以我们很快就能想到一个统计方案：
one_num = 0 for i in bin(4523)[2:]: if i == '1': count += 1 print(f'数字4523的二进制值里面，一共有{count}个1')
运行效果如下图所示：
如果使用这个方法，由于4523的二进制值有13位，所以 for 循环需要执行13次才能完成统计。更一般的结论，一个正整数 n，它的二进制值有位，所以这种解法的时间复杂度始终为O(logn)，那么我们有没有什么办法优化这个算法呢？
这个时候，我们观察一个现象：
给出一个二进制的值1000110101011与这个值减1的值1000110101010，他们做与运算，结果为：1000110101010。可以看到，最右侧的1变成了0.
现在我们再对1000110101010与它减1的值做与运算：
1000110101010 & 1000110101001 = 1000110101000
此时，最右侧的1又变成了0.
我们可以证明，假设有一个二进制数 n与n-1做与运算，它的效果相当于把这个二进制数最右侧的1变成0.
于是，给定一个正整数x，只需要统计移除多少位的最右侧的1以后，这个数字变成了0，就能知道它里面有多少个1.于是我们可以写出如下的代码：
count = 0 n = 4523 while n: n = n & (n - 1) count += 1 print(count)
运行效果如下图所示：
使用这种算法，最坏情况下，只有在数字 n 对应的二进制全部都是1的情况下(3, 7, 15, 31, 63....)，会执行次循环。而一般情况下，如果只有1个1，那么只需要循环1次，如果有2个1，只需要循环2次。大大提高了运算效率。
