AcWing 801. 二进制中1的个数

摘要：
lowbit的经典应用。

题目

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

本题考查二进制，运用lowbit可快速得出结果。

lowbit

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

详情请参考：位运算妙妙屋

#include <iostream>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    for (; n --;) {
        int x, s = 0;
        scanf("%d", &x);
        for (; x; x -= x & -x) s ++ ;
        printf("%d ", s);
    }
    return 0;
}

对于每个数，循环减去最后一个1，直到数字变成0。每次减1，res加1.
注意，这里的减1是指减最后一个1包括后面的所有0.

更多算法请参考：LeetCode 191. 位1的个数

原题链接： AcWing 801. 二进制中1的个数