描述

题目描述

首先我们要注意这么一个问题，本题是 多组输入！，然后我们给定一个正整数，我们要求他的二进制下 1 的个数

这里我们要对数据范围敏感一点 $2 ^ {32} - 1$ 次方，所以我们知道他是int类型的数据

样例解释

首先给定的这个正整数是 5，那么我们把它化成为二进制，我们可以发现是这样的，101，我们可以发现有两个1，所以我们最后的答案就是

知识点: 考察基本的位运算的知识，也可使用C++的STL容器

难度: 一星

题解：

解题思路：

首先我们拿到了一个int类型的正整数，我们要判断有多少位二进制是一，那我们的第一个想法就可以是我们每次判断这位的最后一位是否是1，然后进行一个移位操作，把最后一位剔除掉，这样我们就可以判断出来需要多少次操作,这里为什么 & 1可以判断最后一位是什么呢？我们如图所示：

alt 然后我们运算完之后会发现这么一个有趣的事情，答案是1 alt 这个就是我们的最后的答案我们在换一个数字试试看 alt 我们会发现，这次的这个结果就是等于了0 alt 所以我们发现了，这么一个有趣的性质，就是如果最后一个数 &1 等于1，那么说明这个数字是奇数，也可以说明这个数字的最后低位二进制为1，如果 &1 等于0，那么说明这个数字是个偶数，并且这个数字的最低位的二进制是0，那么我们按照这个思路，我们就是可以想出这么一个算法，运用二进制运算来求取出来我们二进制位1的个数

解法一：运用位运算进行操作

Python 代码实现

if __name__ == "__main__":
    while True: # 多组输入
        try:
            n = int(input()) # 输入一个 n
            res = 0 # 先把最后的答案置为 0
            while n != 0: # 如果 n 最后还有值
                if n & 1 == 1: # 如果 n 的最后一位二进制位是 1
                    res += 1   # 那么我们把最后的答案加 1
                n >>= 1 # 我们把n的最后一位向右移，将其剔除掉
            print(res) # 输出我们最后的答案
        except EOFError:
            break

C++ 代码实现

#include <iostream>
using namespace std;

int n, res; // 定义我们输入的 n 和我们最后的二进制1的个数
void solve() {
    while(cin >> n) { // 多组输入我们的 n
        res = 0; // 因为是多组输入，我们把我们每次的答案都先清空为 0
        while(n) { // 如果 n 还有数字，不为0
            if (n & 1) res++; // 如果当前 n 的最后一位二进制位是 1， 答案加1
            n >>= 1; // n 向右移一次，将刚才计算过的二进制位剔除掉
        }
        cout << res << "\n"; // 输出最后的一个答案
    }
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}

时空复杂度分析

时间复杂度是 $O (l o g n)$ ，解释如下：

首先因为我们是基于二进制位进行的操作，所以我们的时间复杂度就很好计算，因为我们进行操作的就是一个数有多少个二进制位，那么我们就会有多少个操作，也就是说我们的时间复杂度是 $O (l o g n)$ 的

空间复杂度是 $O (1)$ 的我们空间复杂度，因为我们没有引用到新的空间，所以我们的空间复杂度是 $O (1)$ 的

图片解释算法原理

alt alt alt alt alt alt alt alt alt alt alt alt

解法二： STL容器

在我们的C++语言中，有一个神器它叫做STL，这里面封装好了很多我们所需要的一些数据结构，让我们写起来算法更加方便和便捷，这里我们使用了一个名为 bitset 的容器，它可以自动把一个整数，变成二进制模式，里面有很多库函数，比如我们这里就是需要到了其中的一个，叫做 count 的库函数，我们可以用这个来求取出来二进制有多少位 1

c++代码实现

#include <iostream>
#include <bitset> // bitset在这个bitset的库里
using namespace std;

void solve() {
    int n;
    while(cin >> n) { // 多组输入一个n
        bitset<32> a = n; // 建立一个bitset，这个尖括号里面存的是位数，将n变成二进制存到a中
        cout << a.count() << "\n";  // 调用bitset的库函数输出二进制里面的1
    }
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}

时空复杂度分析：

时间复杂度是 $O (l o g n)$ ，解释如下：因为我们的这个n，化成二进制最多是32位，而我们只是对于他的二进制位进行操作，所以我们只要判断n的二进制位有多少即可，所以这里我们就是 $O (l o g n)$

空间复杂度是 $O (l o g n)$ ，解释如下：因为我们的同样n最多就是可以分解出来的就是 $l o g n$ 位，那么其实我们的大小就是log级别的，所以这里的空间复杂度也是 $O (l o g n)$

bitset简单介绍

这里我们给出这个 bitset 这个容器的一个复杂度，这个容器的复杂度，我们先从简单的一个空间复杂度来讲，bitset的每一个位他是一个bit，而一个int在一般的电脑上面是4个字节（byte）而1 byte = 8 bit 这样看我们把这个bitset可以把一个int类型的空间降为 $\frac{1}{32}$ ，其实时间复杂度如果不严格的来讲，我们也是可以理解为是 $\frac{1}{32}$ ，但是其实一般来讲是有以下的四种说法

O(n), 这种记法认为bitset完全没有优化复杂度
O( $\frac{n}{32}$ ), 这种记法不是很严谨(一般来讲我们复杂度里面不应该有常数，我们取得应该是瓶颈复杂度)，但是这个计算方法体现出来了bitset能将所需要的时间优化到 $\frac{1}{32}$
O( $\frac{n}{w}$ ), 这样其中的 w = 32（计算机的位数），这种记法较为普遍的接受
O( $\frac{n}{log w}$ )，其中w为计算机中的一个整形变量的大小

这个总体介绍过于复杂，我们可以简单理解为它可以省下来空间和时间，它开辟的空间位数就是log级别的，但是又是因为它是对比特进行的操作，所以实际空间的使用会更小，但是我们这里粗略理解为log即可

题解 | #查找输入整数二进制中1的个数-两种解决办法含有详细解释#

描述