题目的主要信息：

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

方法一：转化二进制字符串

具体做法：

我们可以将十进制整数转化成二进制后，再统计二进制中1的个数，鉴于二进制位数较多，我们用字符串表示。采用连除法，对数字连续除2取余获取二进制每一位。然后遍历二进制字符串，得到二进制中1的个数。

#include<iostream>
#include<string>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        int count = 0;
        string s = "";
        while(n){ //十进制转化成二进制
            s += ((n % 2) + '0'); //用字符串记录二进制每一位
            n /= 2;
        }
        for(int i = 0; i < s.length(); i++) //遍历字符串统计1的个数
            if(s[i] == '1')
                count++;
        cout<< count << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，连除法一共要循环$lo{g}_{2}nlog\_2n$次，而字符串的长度也不会超过这个数
• 空间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，记录二进制的字符串的长度，不会超过循环的次数

方法二：移位运算和位与运算

具体做法：

任何数与1做位与运算，其结果是该数二进制末尾的数与1做与运算的结果。因此我们可以从后往前不断求1的个数，利用右移位运算来不断去掉最末尾的一位，每次都与1做位与运算就可以了。

#include<iostream>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        int count = 0;
        while(n){
            if(n & 1) //和最后一位按位与运算
                count++; //与的结果是1说明这位是1
            n >>= 1; //移位
        }
        cout<< count << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，移位的次数不会超过该数二进制的有效位，与连除法是一致的
• 空间复杂度：$O(1)O(1)$，无额外空间

方法三：位与运算去掉二进制末尾1

具体做法：

位与运算还有一个性质：n&n-1结果会去掉$nn$的最末尾的1。比如1110&1101=1100，直接就去掉了$11101110$最后的1，我们依照这个性质，不断去掉$nn$末尾的1，直到结果为全0，去掉过程中统计去掉过多少次，即1出现的次数。

#include<iostream>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        int count = 0;
        while(n){
            count++; //统计+1
            n &= (n - 1); //去掉末尾的1
        }
        cout<< count << endl; //输出
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，最坏情况下全是1，还是要循环$nn$的二进制有效位那么多次
• 空间复杂度：$O(1)O(1)$，无额外空间

方法四：库函数

具体做法：

将数字转变成32个bitset型变量，然后统计个数即是1的个数。

#include<iostream>
#include<bitset>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        bitset<32> bit(n); //转换32位二进制类
        cout << bit.count() << endl; //直接输出位数
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，转变成bitset型要遍历数字每位，统计的时候最坏情况下全是1，还是要循环$nn$的二进制有效位那么多次
• 空间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，bitset类变量的空间