LeetCode 191 Number of 1 Bits

位1的个数

题意

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 1 的个数.

示例 1：

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

示例 2：

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

示例 3：

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

解法一

这里用到了位运算, 如数字 5, 二进制位为 101, 那么使用 & 运算, 和 1 进行与运算, 如:

  101
& 001
-----
  001

因为 1 只有最后一位为 1, 其他为都是 0, 所以他与任何数进行 & 运算后, 都只会保留这个数的最后一位, 如果运算结果还是 1, 说明这个树的最后一位是 1, 反之为 0.

那就很好解决了, 将 num & 1 后判断为 1, 则计数增加 1, 然后将右移一位 num >>= 1, 以此类推, 直到移位 32 次.

public class Solution {
    public int hammingWeight(int n) {
        int bits = 0;
        int mask = 1;
        for (int i = 0; i < 32; i++) {
            if ((n & mask) != 0) {
                bits++;
            }
            n >>= 1;
        }
        return bits;
    }
}

时间复杂度 O(1), 空间复杂度 O(1).

解法二

这个解法有些取巧, 在二进制表示中，数字 n 中最低位的 1 总是对应 n - 1 中的 0. 因此, 将 n 和 n - 1 与运算总是能把 n 中最低位的 1 变成 0, 并保持其他位不变.

如对于数字 10, 和 10 - 1 进行 & 运算:

  1010
& 1001
------
  1000

接着对于二进制值 1000, 与 999 进行 & 运算:

  1000
&  999
------
  0000

由于每次都把最低位的 1 变为 0 了, 直到为 0, 那么这种个编程变了几次就说明有多少个 1.

public class Solution {
    public int hammingWeight(int n) {
        int sum = 0;
        while (n != 0) {
            sum++;
            n &= (n - 1);
        }
        return sum;
    }
}

时间复杂度 O(1), 空间复杂度 O(1). 但此算法效率相对比算法一效率高.