54 - 位1的个数

题目

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

示例 1：

输入：00000000000000000000000000001011 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

输入：00000000000000000000000010000000 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

输入：11111111111111111111111111111101 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示：

• 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。

• 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

进阶: 如果多次调用这个函数，你将如何优化你的算法？

解答

数一下二进制总有几个1。

var hammingWeight = function (n) {
  let bit = 0
  mask = 1
  for (let i = 0; i < 32; i++) {
    if ((n & mask) != 0) {
      bit++
    }
    mask <<= 1
  }
  return bit
};

Runtime: 64 ms, faster than 61.73% of JavaScript online submissions for Number of 1 Bits.

Memory Usage: 34.9 MB, less than 30.00% of JavaScript online submissions for Number of 1 Bits.

第五行n & mask，是用来判断该位是否为1。因为&，是两边都为1的时候，才会输出1，否则返回0。

而1的32位无符号为：

0000 0000 0000 0000 0000 0000 0000 0001

也就是在判断n的最后一位，是否为1。是1的话就让计数的bit加一。

第八行的mask<<=1，也就是mask = mask << 1，是让mask向左移动一位，右边补0，最左的丢弃。也就变成了

0000 0000 0000 0000 0000 0000 0000 0010

换言之是在一位位检验是否对应数字为1。

骚操作

一位位比对太麻烦，这个骚操作，能每次让n的最后一位1变成0。这样只要n不为0，就说明还有1，还能继续加1。

那么什么操作能让最后一位1变成0呢？n &=(n-1)

做完这个操作之后，其他位不变，就最后一位变成0了。

func hammingWeight(num uint32) int {
    sum := 0
    for num != 0 {
        sum++
        num &= num - 1
    }
    return sum
}

Runtime: 0 ms, faster than 100.00% of Go online submissions forNumber of 1 Bits.

Memory Usage: 2 MB, less than 100.00% of Go online submissions forNumber of 1 Bits.

var hammingWeight = function (n) {
  let sum = 0
  while (n != 0) {
    sum++
    n &= n - 1
  }
  return sum
};

Runtime: 60 ms, faster than 82.90% of JavaScript online submissions for Number of 1 Bits.

Memory Usage: 34.9 MB, less than 30.00% of JavaScript online submissions for Number of 1 Bits.