位 1 的个数
Number of 1 Bits
本机进度仅保存在当前浏览器
题目描述
编写一个函数，输入是一个无符号整数（二进制串形式），返回其二进制表达式中数字位数为 1 的个数（也称汉明重量）。
示例：n = 11（二进制 1011），输出 3。
解题思路
- 逐位检查是 O(log n)；Brian Kernighan 技巧 n &= n - 1 每次消除最低位的 1，循环次数恰为 1 的个数。
- 原理：n - 1 会把最低位的 1 变 0、其后的 0 变 1，按位与恰好把这最低位的 1 清掉。
参考实现
查看参考实现Python · 建议先自行作答
def hammingWeight(n):
# n & (n-1) 消除最低位的 1
count = 0
while n:
n &= n - 1
count += 1
return count