位运算-二进制中1的个数

题目

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

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

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

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

数据范围 $1≤n≤100000$,$0≤数列中元素的值≤10e9$ 输入样例：

5
1 2 3 4 5

输出样例：

1 1 2 1 2

思路

位运算常用的两个方法 求 $n$ 的第 $k$ 位数字: n >> k & 1 返回 $n$ 的最后一位 $1$：lowbit(n) = n & -n

代码

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x, s = 0;
        cin >> x;
        for (int i = x; i; i -= i & -i) s ++ ;  // 只加当前位为1的情况
        cout << s << " ";
    }
    
    return 0;
}