二进制中1的个数

位运算概述

原码，反码，补码的关系
1. 原码就是一个数字本身的二进制表示
2. 反码是原码按位取反得到的
3. 补码是反码$+1$

位运算常用操作就是两个
1. 求n的第k位数字: n >> k & 1
n >> k，先把第k位移到最后，再 & 1，查看最后一位是什么
2. 返回n的最后一位1：lowbit(n) = n & -n

第一个好理解，第二个举个例子，$n = 1010100$，那么$n$ & $-n = 10101$也就是说后面的$0$都给抹掉了

本题思路分析

1. 如果用第一个模板，每一个位数进行枚举，那么时间复杂度，$n$是二进制数的位数，$O(n^2)$

2. 所以用第二个模板
   每次把最后一个1减掉，那么时间复杂度就是$O(n)$的(可能更小)

代码

#include <iostream>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int x, s = 0;
        scanf("%d", &x);

        for (int i = x; i; i -= i & -i) s ++ ;//每次将数字末位的1减去

        printf("%d ", s);
    }

    return 0;
}