二进制中1的个数

题目描述

请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
示例 1：

1
2
3

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

示例 2：

1
2
3

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

示例 3：

1
2
3

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

提示：
输入必须是长度为 32 的 二进制串 。

题目链接

Leetcode

题目解答

解法一

整数转二进制，使用Integer的toBinaryString()方法可以直接得到整数的二进制字符串，然后统计字符串中1出现的次数即可。

时间复杂度:$O(n)$ 空间复杂度:$O(1)$

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        String str = Integer.toBinaryString(n);
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '1') {
                count++;
            }
        }
        return count;
    }
}

执行用时：2 ms, 在所有 Java 提交中击败了96.88%的用户
内存消耗：35.6 MB, 在所有 Java 提交中击败了19.39%的用户

解法二

1	n & (n - 1) // 消除二进制中最右边的1

示例

  1 0 1 0 // 10
& 1 0 0 1 // 9
---------
  1 0 0 0 // 10 & 9 消除了10二进制中最右边的1
-----------------------------------------
  1 0 0 0 // 8
& 0 1 1 1 // 7
---------
  0 0 0 0 // 8 & 7 消除了8二进制中最右边的1

位运算，通过上述示例可以看出，一个数能进行多少次 n&(n-1)操作，其对应的二进制数就包含多少个1，且运算最终结果为0。

时间复杂度:$O(k)$ 空间复杂度:$O(1)$

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }
}

执行用时：1 ms, 在所有 Java 提交中击败了96.88%的用户
内存消耗：35.3 MB, 在所有 Java 提交中击败了70.23%的用户