题目内容

给定一个长度为n的数列，请你求出数列中每个数的二进制表示中1的个数。

输入格式

第一行包含整数n。
第二行包含n个整数，表示整个数列。

输出格式

共一行，包含n个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中1的个数。

数据范围

1≤n≤100000,
0≤数列中元素的值≤10^9

输入样例

5
1 2 3 4 5

输出样例

1 1 2 1 2

题解

首先，求解此题需要知道一个知识点：lowbit操作，即返回x的最后一位的1。
lowbit操作：res = x & -x = x & (~x + 1)

本题中，需要针对每个数字求其中二进制表示的1的个数，那么我们只需要将每个数的二进制表示中的1依次去掉，并进行累加，分别求每一个数的1的个数即可。在运算的过程中，会用到之前提到的知识点，具体请看代码实现。

代码

#include <iostream>
using namespace std;

int lowbit(int x){
    return x & -x;
}

int main(){
    int n;
    cin >> n;
    
    while(n--){
        int x;
        cin >> x;
        int res = 0;
        while(x) x -= lowbit(x),res++;//每次减去x的最后一位1
        
        cout << res << ' ';
    }
    return 0;
}