题目的主要信息：

• 输入一个十进制int型整数，计算其二进制中1的个数

方法一：转化二进制

具体做法：

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

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

int main(){
    int n;
    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;
    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;
    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)$，无额外空间