题目描述

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

输入格式

第一行包含整数n。

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

输出格式

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

数据范围

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

样例

输入样例：

5
1 2 3 4 5
输出样例：

1 1 2 1 2

算法1

(位运算) $O(n)$

计算机对整数以补码形式存储
采用补码与原码的关系：
正数，原码和补码一样；
负数，对原码按位取反，末位加1，不包括符号位，可转换为补码，反之亦可。

负数，补码和原码的特点：
从右往左第一个1的位置一样，这个1往右逐位相等，往左，逐位相反
例如：x=-10，原码=1 1010, 补码=1 0110
那-10和10对补码分别为： 1 0110， 0 1010
-10 & 10就会返回第一个相等的位对应的数，即为2

时间复杂度

参考文献

C++ 代码

#include<iostream>

using namespace std;

const int N=1e5+10;

int a[N];

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

int main(){
    int n;
    cin>>n;

    for(int i=0;i<n;i++)    scanf("%d",&a[i]);

    int k,sum;
    for(int i=0;i<n;i++){
        k=a[i];
        sum=0;
        while(k!=0){
            k-=lowbit(k);
            sum++;
        }
        cout<<sum<<" ";
    }


}