191. 位 1 的个数
题目描述
输入正整数 n。统计它的二进制表示里有多少位是 1，返回这个数量。
这个数量也叫汉明重量。
示例 1
输入：n = 11 输出：3
解释：11 的二进制是 1011，含 3 个 1。
示例 2
输入：n = 128 输出：1
解释：128 的二进制是 10000000，只有 1 个 1。
示例 3
输入：n = 2147483645 输出：30
解释：2147483645 的二进制是 31 位，仅倒数第二位为 0，所以有 30 个 1。
数据范围
1 <= n <= 2^31 - 1
进阶：如果这个函数需要被反复调用，可以怎样优化？
解题思路：n & (n-1) 消去最低位 1
利用 n & (n - 1)：n - 1 会把 n 最低位的 1 变成 0、并把它右边的 0 全变成 1，再与 n 相与，就恰好消掉了最低位的那个 1。不断执行直到 n 为 0，执行的次数就是 1 的个数。
为什么正确
cnt + popcount(n) 始终等于原数的 1 的个数；每轮 n 恰好少一个 1。
复杂度分析
时间 O(k)，k 为 1 的个数（至多 31）；空间 O(1)。
易错点
逐位右移统计也可以，但要循环 32 次；若输入可能是负数（如老版本题目），JS/Java 用 >> 会补符号位导致死循环，n & (n - 1) 写法在 32 位整型下也能在至多 32 轮内结束。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def hammingWeight(self, n: int) -> int:
cnt = 0
while n:
n &= n - 1
cnt += 1
return cntclass Solution {
public int hammingWeight(int n) {
int cnt = 0;
while (n != 0) {
n &= n - 1;
cnt++;
}
return cnt;
}
}class Solution {
public:
int hammingWeight(int n) {
int cnt = 0;
while (n) {
n &= n - 1;
cnt++;
}
return cnt;
}
};func hammingWeight(n int) int {
cnt := 0
for n != 0 {
n &= n - 1
cnt++
}
return cnt
}var hammingWeight = function(n) {
let cnt = 0;
while (n) {
n &= n - 1;
cnt++;
}
return cnt;
};function hammingWeight(n: number): number {
let cnt = 0;
while (n) {
n &= n - 1;
cnt++;
}
return cnt;
}其他解法
逐位检查固定循环 32 次；n & (n-1) 每次直接消掉最低位的 1，循环次数等于 1 的个数。
解法 2：逐位检查 时间 O(k)，k=32，空间 O(1)
依次检查第 0 到第 31 位：用 n & (1 << i) 判断这一位是否为 1，是就计数加一。
最直接的写法，不需要任何技巧。无论有多少个 1 都要检查全部 32 位。
class Solution:
def hammingWeight(self, n: int) -> int:
cnt = 0
for i in range(32):
if n & (1 << i):
cnt += 1
return cntclass Solution {
public int hammingWeight(int n) {
int cnt = 0;
for (int i = 0; i < 32; i++) {
if ((n & (1 << i)) != 0) cnt++;
}
return cnt;
}
}class Solution {
public:
int hammingWeight(int n) {
unsigned x = n;
int cnt = 0;
for (int i = 0; i < 32; i++) {
if (x & (1u << i)) cnt++;
}
return cnt;
}
};func hammingWeight(n int) int {
cnt := 0
for i := 0; i < 32; i++ {
if n&(1<<i) != 0 {
cnt++
}
}
return cnt
}var hammingWeight = function(n) {
let cnt = 0;
for (let i = 0; i < 32; i++) {
if ((n & (1 << i)) !== 0) cnt++;
}
return cnt;
};function hammingWeight(n: number): number {
let cnt = 0;
for (let i = 0; i < 32; i++) {
if ((n & (1 << i)) !== 0) cnt++;
}
return cnt;
}