Write a function that takes an unsigned integer and return the number of '1' bits it has (also known as the Hamming weight).

Example 1:
Input: 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bit.

Example 2:
Input: 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:
Input: 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Note:

  • Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3 above the input represents the signed integer -3.

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

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

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

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

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

0000 0000 0010 0011
0000 0000 0010 0010
-------------------
0000 0000 0010 0010

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

0000 0000 0010 0010
0000 0000 0010 0001
-------------------
0000 0000 0010 0000

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

0000 0000 0010 0000
0000 0000 0001 1111
-------------------
0000 0000 0000 0000

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

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

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

int hammingWeight(uint32_t n) {
    if (!n)
        return 0;
    uint8_t sum;
    for (sum = 0; n; sum++) {
        n &= (n - 1);
    }
    return sum;
}