题目的主要信息：

输入一个正整数，计算它在二进制下的1的个数。

方法一：

移位统计。每次判断n的二进制的最低位是否为1，更新统计变量count。然后将n向右移动一位，直至判断完所有位。 具体做法：

#include<iostream>

using namespace std;

int main(){
    int n;
    while(cin >> n){
        int count = 0;
        while(n > 0){
            if(n & 1){//看最低位是否为1
                ++count;
            }
            n >>= 1;//向右移动一位
        }
        cout << count << endl;
    }
    
    return 0;
}

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，n转换为二进制后，总共有$lo{g}_{2}nlog\_2n$位。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。

方法二：

用位图。将整数n转为位图，利用位图的函数count输出1的个数。bitset的每一个元素只能是０或１，每个元素仅用１bit空间。

具体做法：

#include <iostream>
#include <bitset>

using namespace std;

int main(){
    int n;
    while(cin >> n){
        bitset<32> bs(n);//转为位图
        cout << bs.count() << endl;//输出位图中的1的个数
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，count函数的时间复杂度为$O(lo{g}_{2}n)O(log\_2n)$。
• 空间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，n转为bitset的大小为$lo{g}_{2}nlog\_2n$位。