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

题目链接:https://www.acwing.com/problem/content/description/803/
时/空限制：1s / 64MB

题目描述

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

解题思路

题意:求一个数二进制中1的个数。
思路:这个方法就多了，我们可以利用n >> k & 1求n的第k位数字，然后判断是不是1就行了，还有就是可以利用n & -n，返回n最后一位1，我们将每其减去，就相当于每消去一个1，直到n为0为止，减的过程中统计一下就行了。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int lowbit(int x) {
    return x & -x;
}
int Count(int n) {
    int res = 0;
    while (n) {
        res++;
        n -= lowbit(n);
    }
    return res;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        printf("%d%c", Count(x), "\n "[i < n - 1]);
    }
    return 0;
}