题目分析

1. 题目给出我们一个int型整数
2. 我们要输出这个整数转换成二进制后的1的个数

方法一：位运算

• 实现思路
  • 由于我们要针对二进制进行操作
  • 因此很容易想到位运算可以逐位处理二进制数位
  • 我们循环将给定整数右移一位，并每次与1取与运算
  • 统计与运算结果的和就是最终结果

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    int count = 0;
    while(n) {				
        count += (n & 1);		// 数字和1取与运算，来获得最后一位的信息
        n >>= 1;				  // 不断迭代n右移一位
    }
    cout << count;
    return 0;
}

复杂度分析

• 时间复杂度：$O(1)O(1)$，由于处理的数字是int范围数字，最长也是32位
• 空间复杂度：$O(1)O(1)$，未引入额外的空间开销

方法二：bitset结构

• 实现思路

  • c++有支持储存整数二进制位的数据结构bitset

  • 其存储的每一位的空间开销也只是按位计算的，而不是按照int类型来计算的

  • 我们只要将整数存储在bitset中，遍历每一位即可

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>

using namespace std;

int main() {
    int n;
    int count;
    cin >> n;
    bitset<32> num(n);				// 引入bitset结构存储
    for(int i = 0; i < 32; i++){	// 遍历bitset结构的每一位进行计数
        if(num[i] == 1) count++;
    }
    cout << count;
    return 0;
}

复杂度分析

• 时间复杂度：$O(1)O(1)$，由于处理的数字是int范围数字，最长也是32位
• 空间复杂度：$O(1)O(1)$，最大的bitset结构开销也是32位的级别，因此可以视作$O(1)O(1)$