15. 二进制中1的个数【位运算】

1. 问题

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

示例 1：

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

示例 2：

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

示例 3：

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

2. 解法① - 逐位判断

Java 移位运算符

  1. <<：左移运算符，左移几位就补几个0。

  2. >>：右移运算符（算术右移），如果数字为正数时，移位后在前面补0，为负数时，则在前面补1。

  3. >>>：无符号右移运算符（逻辑右移），忽略符号，空位补0即可。

2.1 Java

public class Solution {
    public int hammingWeight(int n) {
        /**
         * 根据位运算的定义：
         *  1. 如果n&1=0，那么n二进制的最右位是0
         *  2. 如果n&1=1，那么n二进制的最右位是1
         */

        // n二进制中1的个数
        int num = 0;

        /**
         * 本题中n为无符号数，所以右移时使用无符号右移
         * 无符号右移：不管符号位，右移时往最左边补0即可
         */
        while(n != 0) {
            // 如果n的最右边是1，那么n&1=1，所以1的个数就加一
            // 如果n的最右边是0，那么n&1=0，所以1个个数不变
            num += n & 1;

            // 每次判断完最右位数字就将n右移一位
            n >>>= 1;            
        }

        return num;
    }
}

3. 解法② - 使用n&(n−1)

3.1 Java

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        // 利用 n&(n−1)
        // n       = 100100100000
        // n-1     = 100100011111
        // n&(n-1) = 100100000000
        // 所以n和n-1的&操作会消去n最右边的1
        // 只要算出n变为0总共做了几次&操作即可求解1的个数
        int num = 0;
        while (n != 0) {
            n = n & (n - 1);
            num++;
        }
        return num;
    }
}

3.2 复杂度分析

时间复杂度：O(M)

  • n&(n−1)操作只有【减法】和【与】运算，占用O(1)；设M为二进制数字n中1的个数，那么需要循环M次（每次消去一个1），所以是O(M)。

空间复杂度：O(1)

  • 变量ans占用常数空间。

4. 参考

上一页14-II. 剪绳子 II【贪心】下一页16. 数值的整数次方【分治】

最后更新于