题目描述

求解二进制中1的个数

样例

输入：

5
1 2 3 4 5

输出：

1 1 2 1 2

输出的每个数表示输入的每个数二进制表示中1的个数

算法

依次右移位，判断移位后的数和1于一下是否为真

时间复杂度 求解每个数二进制位为1的个数的复杂度是O(log(n))

C++ 代码

#include <iostream>
using namespace std;
int count_bin1(int x){
    int res = 0;
    while(x){
        res+=x&1;
        x>>=1;
    }
    return res;
}

int main(){
    int n;
    cin>>n;
    int x;
    while(cin>>x){
        cout<<count_bin1(x)<<' ';
    }
}