【leetcode】22. 位操作-二进制中1的个数

发表于 更新于 分类于 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 1 分钟

题目

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

示例 1：

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

示例 2：

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

示例 3：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

方法一

分析

本题一种暴力的解法就是循环判断n的每一位是否为1。
时间复杂度：O(1)，可以算作O(1)的时间复杂度了，毕竟循环32次就行了。
空间复杂度：O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while(n) {
            cnt += n & 1;//只判断最后一位
            n >>= 1;
        }
        return cnt;
    }
};

方法二

分析

n-1会将n最左侧的1变成0，同最左侧的0变成1。如：

n: 00000000000000000000000000001011
n-1: 00000000000000000000000000001010
n&(n-1): 00000000000000000000000000001010
n: 00000000000000000000000000001000
n-1: 00000000000000000000000000000111
n&(n-1): 00000000000000000000000000000000

从上面可以看出，n&(n-1)可以消去n最左侧的1,从而使得遍历次数为1的个数。
时间复杂度：O(1)，可以算作O(1)的时间复杂度了，循环最多32次就行了。
空间复杂度：O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while (n) {
            res ++;
            n &=(n-1);
        }
        return res;
    }
};