Day 29 - 191.number of 1 bits

Day29 - 191.位1的个数

LeetCode 191.位1的个数

题目链接：

https://leetcode.cn/problems/number-of-1-bits/

1. 题目描述

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

2. 思路解析

3. 方法零

按照题目要求，先转化为二进制再计数。可以叫做暴力算法，但是时间复杂度也不高。

3.1. C++代码

class Solution
{
public:
    int hammingWeight(int n)
    {
        vector<int> bin;
        int temp = n;
        int i = 0;
        while(temp != 0)
        {
            // 可以使用insert，这样得到的二进制是正确的二进制
            // 由于只需要计数，顺序不重要，所以push_back亦可以，这里不做演示
            // bin.push_back(temp % 2);

            bin.insert(bin.begin(), temp % 2);
            // 可以使用右移运算来代替 / 2 运算
            temp = temp / 2;
            i++;
        }
        // vector内置方法，计数1
        return count(bin.begin(), bin.end(), 1);
    }
};

4. 方法一

类似方法零。

定义res保存1的个数。对于无符号整数n，统计其中1的个数步骤如下：

1. 如果n != 0，n对应二进制的最右边一位如果是1，res++，进入步骤2。否则，返回res。

2. 把n对应的二进制向右移动一位，进入步骤1。

关键在于如何获取n对应二进制的最右边一位和怎样将n对应的二进制向右移一位。

获取n对应二进制最右面一位有两种方式：

1. n和1进行与运算n & 1可以获取n对应二进制的最右面一位。

2. n对2取余n % 2即可获取n对应二进制的最右面一位。

将n对应的二进制右移一位有两种方式：

1. 直接使用编程语言自带的右移符号，比如c++可以写为n >> 1。

2. n / 2 也可以将n对应的二进制右移一位。

4.1. C++代码

class Solution {
public:
    int hammingWeight(int n)
    {
        int res = 0;
        while(n)
        {
            // 减少存储二进制，计算一位就判断一位
            if(n % 2)
            {
                res++;
            }
            n = n / 2;
        }
        return res;
    }
};

减少存储n的二进制格式，计算一位就判断一位，空间复杂度降为O(1)

另外的写法：

• 加入与运算，提高运算速度。

class Solution {
public:
    int hammingWeight(int n)
    {
        int res = 0;
        while(n)
        {
            // 减少存储二进制，计算一位就判断一位
            // 使用与 1 运算来取出最后一位
            if(n & 1)
            {
                res++;
            }
            // 去掉最后一位
            n = n >> 1;
        }
        return res;
    }
};

5. 方法二

定义res保存1的个数。对于无符号整数n，统计其中1的个数步骤如下：

1. 如果n != 0，res++，进入步骤2。否则，返回res。

2. n = n & (n - 1)，进入步骤1。

n & (n - 1)其实就是将n对应的二进制最右边值为1的bit位置为0。

在纸上继续按照上面步骤模拟一遍，会帮助大家更好的理解。

5.1. C++代码

class Solution
{
public:
    int hammingWeight(int n)
    {
        int res = 0;
        while (n)
        {
            // 根据推理，此公式运行几次就有几个 1
            n = n & (n - 1);
            res++;
        }
        return res;
    }
};

6. 复杂度分析

时间复杂度： 后两种方法都是O(1)，因为二进制最长为32位。

空间复杂度： 后两种方法都是O(1)，只使用了几个整型变量。

7. Redo. 02/07

• n_copy & 1 == 1检验最低位是否为1

• n_copy = n_copy >> 1;更新迭代，去除最低位

• while(n_copy)直到全位为0为止

class Solution
{
public:
    int hammingWeight(int n)
    {
        int n_copy = n;
        int res = 0;
        while(n_copy)
        {
            if(n_copy & 1 == 1)
            {
                res++;
            }
            n_copy  = n_copy >> 1;
        }
        return res;
    }
};