二进制数中 1 的个数

二进制数中 1 的个数这个问题可以说是很常见的基础问题了。

最简单最慢的方法就是转换成字符串查 1 的数量。

比较快的方法是使用位运算。

举例来说,整数 35,用二进制表示就是 0000 0000 0010 0011,二进制数中有 3 个 1。
计算这个数字中的 1 的个数,使用与运算便可以快速完成。

这里有个位运算的小知识,n & (n-1) 可以消去二进制数的最右边的 1。
比如 35 & 34

1
2
3
4
0000 0000 0010 0011
0000 0000 0010 0010
-------------------
0000 0000 0010 0010

结果得到 34,接下来 34 & 33

1
2
3
4
0000 0000 0010 0010
0000 0000 0010 0001
-------------------
0000 0000 0010 0000

结果得到 32,接下来 32 & 31

1
2
3
4
0000 0000 0010 0000
0000 0000 0001 1111
-------------------
0000 0000 0000 0000

结果得到 0,计算过程便完成了。

在得到 0 之前,一共计算了 3 次,也就是说一共消去了 3 个 1。
即,给定数字 35,得出结果为 3

使用 C 语言表示以上算法:

1
2
3
4
5
6
7
8
9
int hammingWeight(uint32_t n) {
if (!n)
return 0;
uint8_t sum;
for (sum = 0; n; sum++) {
n &= (n - 1);
}
return sum;
}

0%