位操作

二进制中1的个数

在计算机底层的世界里，只有0和1，我们通过对二进制的操作来巧妙的进行运算。

位操作符号

• ”»” 这个符号是右移
• ”«” 这个符号是左移
• “&” 这个符号是与运算

• ”	” 这个符号是或运算

• ”^” 这个符号是异或运算

左移右移代表计算机的乘2和除以2，与运算法则是一假全假，或运算法则是一真全真，异或运算法则是不进位的加法，也可以这样计算，同0异1。

现在我们回归正题，怎么利用位运算来判断一个正整数 $(0 \le x \le 10^9)$ 的二进制里有多少个1。

我们先介绍一个补码：

• 计算机里存的数都是以补码的形式存在
• 正数的补码还是自己本身
• 负数的补码是最高位符号位不变，其余变反码，再+1

有了这个性质我们可以再研究下去

正整数自然不必纠结，而负整数它首先要除最高位其他位都要按位取反，我们发现如果现在正数和添负号的反码两个做与运算，发现一个规律，结果所有位都变成了0，负数的补码要在反码的基础上+1，这是最关键的一点，反码+1之后，就发现正数末尾1之后的都和补码末尾1之后的一样了，这点就起了至关重要的作用末尾1前面的所有位都经过与运算变为了0，而末尾1之后的不变，与运算之后我们就得到了末尾的1。

以上就是二进制中1的个数算法的精髓

代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int a[N];
int n;

// low_bit函数
int low_bit(int x)
{
    return x & (-x);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    
    for (int i = 0; i < n; i++)
    {
        int x= a[i];
        int j = 0;
        // 每次low_bit得到低位的1就删去，计数，直到这个数为0。
        while (x)
        {
            x -= low_bit(x);
            j++;
        }
        printf("%d ", j);
    }
    return 0;
}