题目描述

给定一个长度为 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

(位运算) $O(n)左右$

一般做法（很好懂），“x-=x&-x”

这样做的目的是：求出x的最后一位1，再把它减掉

因为计算机当前存储用的是补码

不知什么情况，c++的按位与用的也是补码

这里的x是一个正数。所以-x就是一个负数（不考虑0的情况）

“正数的补码是它本身，负数的补码是除符号位外按位取反再加一”（二进制）

所以x&-x，很明显，大多数的位都会因为按位取反直接归零。

但因为那个“再加一”，会把原数的最后一位1挑出来。

下面是例子（没写符号位）：

x=10001000（瞎写的）

-x的补码=01110111+1=01111000

所以两个一按位与，就变成了00001000

实际上，“x&=x-1”可以直接达成这个效果~

因为，当计算机在算二进制的x-1时

x=10001000（还是瞎写的）

x-1=10000111

所以x&x-1=10000000

最后一位“1”神奇地被去掉了~

时间复杂度

O(n)左右

具体的要看每一个数的二进制表示有几个“1”

C++ 代码

#include<iostream>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int x,ans=0;
        scanf("%d",&x);
        while(x){
            x&=x-1;
            ans++;
        }
        printf("%d ",ans);
    }
}