题目描述

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

输入格式
第一行包含整数n。

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

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

数据范围
1≤n≤100000,
0≤数列中元素的值≤109

样例

输入样例：
5
1 2 3 4 5
输出样例：
1 1 2 1 2

理解

x&(-x) 返回的是x（二进制）最后一位1；
-x= ~x+1;

  x=10101000
 ~x=01010111
~x+1=01011000

x&(-x+1)=00001000

然会就循环x-=x&(-x)，是1，res就加1

时间复杂度分析：o(1)

C++ 代码

#include<iostream>
using namespace std;

int n;

int main(){
    cin>>n;
    while(n--){
        int x,res=0;
        cin>>x;
        while(x)x-=x&(-x),res++;
        cout<<res<<" ";
    }
    return 0;
}