Lowbit运算
lowbit运算
lowbit运算的结果是返回一个数的二进形式下最后一个1及之后的二进制数。
实现形式（x为一个整数）：
x&(-x)
为什么这样就能实现呢？
首先我们要知道在C++中，关于负数的加减的储存离不开补码的概念。
**
什么是补码？
负数补码的值是在原码的基础上先取反后+1（正数的补码就是它本身），比如：
-1
源码：10000001
反码：11111110
补码：11111111
+1的原码、反码和补码都是：
00000001
那么我们实现1+(-1)时，实际上是他们的补码相加，自然就是00000000
**
现在我们来解释x&(-x)
x&(-x) = x&(~x+1)
大家应该能看得懂上面的等式吧，那么我们假设x为这样一个数:
101110101000...(无序的杂乱无章的0和1)1(最后一个1)0000....(之后全是0)
那么对它取反是：
010001010111...(与原码相反的无序的杂乱无章的0和1)0(最后一个1对应的0)1111....(之后全是1)
那么很容易想到，我们对反码+1后，进位停止于从右往左数的第一个0，也就是说以这个0为界限，它左边的二进制数不会发生变化，而右边包括它自己将会变回与反码相同的数：
010001010111...(与原码相反的无序的杂乱无章的0和1)1(最后一个1)0000....(之后全是0)
这样，当我们用其与原码进行 &(与) 运算时，前面的的部分会因为与原码正好相反而全部得出0，后一部分会因为与原码完全相同而保留下来，从而得出x的二进制情况下最后一个1及之后的二进制数。
lowbit的应用
最常见的应用就是统计x二进制数中1的个数，即当我们每次都用x减去它的lowbit值，并且count++,直到x=0时，我们就能计算出x二进制数中1的个数： 核心代码：
while (n != 0)
{
lowbit = n & (-n);
n -= lowbit;
++count;
}
#include <iostream>
int main()
{
int n,q;
std::cin >> q;
int lowbit, count = 0;
while (q--)
{
std::cin >> n;
while (n != 0)
{
lowbit = n & (-n);
n -= lowbit;
++count;
}
std::cout << count<<" ";
count = 0;
}
}