【模板题】位运算

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

【输入格式】
第一行包含整数 n n n。
第二行包含 n n n个整数，表示整个数列。

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

【数据范围】
1 ≤ n ≤ 100000 1≤n≤100000 1≤n≤100000
0 ≤ 数 列 中 元 素 的 值 ≤ 1 0 9 0≤数列中元素的值≤10^9 0≤数列中元素的值≤109

【输入样例】

5
1 2 3 4 5

【输出样例】

1 1 2 1 2

【分析】

我们可以写一个 l o w b i t ( x ) lowbit(x) lowbit(x)函数返回 x x x的二进制中最低位的 1 1 1所表示的数，那么怎么实现这个功能呢？假设 x = ( 1100100 ) B x=(1100100)_B x=(1100100)B​，那么 − x = ( 0011011 ) B + 1 = ( 0011100 ) B -x=(0011011)_B+1=(0011100)_B −x=(0011011)B​+1=(0011100)B​，则 x & − x = ( 0000100 ) B x&-x=(0000100)_B x&−x=(0000100)B​，也就是 x x x的最低位 1 1 1所表示的数。然后回到本题，我们需要快速计算出某个数的二进制表示中有几个 1 1 1，那我们就可以循环每次将这个数 x x x减去 l o w b i t ( x ) lowbit(x) lowbit(x)，也就是每次循环都把 x x x的最低位 1 1 1减去，每减一次答案加一，等这个数减为 0 0 0时答案就是这个数中 1 1 1的个数。

【代码】

#include 
using namespace std;

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

int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        int x;
        scanf("%d", &x);
        int res = 0;
        //每次减去x的最后一位1
        while (x) x -= lowbit(x), res++;
        printf("%d ", res);
    }
    return 0;
}