二进制中1的个数

AcWing801.二进制中1的个数

  • 求n的第k位数字: n >> k & 1
  • 返回n的最后一位1：lowbit(n) = n & -n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;

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

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