lowbit的概念
我们知道，任何一个正整数都可以被表示成一个二进制数。如：
(2)10=(10)2
(4)10=(100)2
那么定义一个函数f(x) = lowbit(x)，输入一个十进制数，返回二进制中最低一位的1所表示的值，如lowbit(4)=4
先了解原码 补码 反码
原码：是最简单的机器数表示法。用最高位表示符号位，‘1’表示负号，‘0’表示正号。其他位存放该数的二进制的绝对值举例
1010 ： 最高位为‘1’,表示这是一个负数，其他三位为‘010’， 即（0*2^2）+（1*2^1）+（0*2^0）=2（‘^’表示幂运算符） 所以1010表示十进制数（-2） 同理 0010表示十进制数（2）
0001+0010=0011 （1+2=3）ok
0000+1000=1000 （+0+（-0）=-0） ok
0001+1001=1010 （1+（-1）=-2）no
由此引出了反码的概念来解决1 + -1 = -2的问题反码：正数的反码还是等于原码，负数的反码就是他的原码除符号位外，按位取反。举例
若以带符号位的四位二进制数为例： 3是正数，反码与原码相同，则可以表示为0011 -3的原码是1011，符号位保持不变，低三位（011）按位取反得（100）所以-3的反码为1100
0001（1 ）+1110 (- 1)=1111（-7）no 正确答案为0
1110（-1）+1101（-2）=1011（-4）no 正确答案为-3
1110（-1）+1100（-3）=1010（-5）no 正确答案为-4
细心的你可能发现，除了第一个,其他计算错误的结果差值只是相差了1
由此引出了补码的概念来解决问题补码：正数的补码等于他的原码， 负数的补码等于反码+1。也等于正数反码+1。
可能有小伙伴疑惑为什么 0001（1 ）+1110 (- 1)=1111（-7）no 正确答案为0 如果这个+1不是会错误吗?? 哈哈，显然不是 机器码的位数在操作系统中是固定位，假设只有4位 源码 1 : 0001 -1:1001 补码 1 ：0001 -1:1110 + 1 = 1111 补码相加 1 + -1 = 0001 + 1111 = 10000，因为保留4位，所以最终结果为0000 nice~~完美
负数的补码等于反码+1，也等于正数反码+1。 1. -1 ：1001 -> 1111 2. -1 : (1: 0001)的反码 1110 + 1 -> 1111
lowbit函数有两种实现方法：
1.
x&(x^(x-1))
2.
x&-x
我们先来解释第一个，还是先拿(6)10举例
(6)10-(1)10=(5)10
(110)2-1=(101)2
我们发现，根据小学数学减法运算的借位原则（滑稽），对一个二进制数进行减1，那么会出现从这个这个数的最后一个1开始到最后的所有数都取反，即构成一个01111⋯的串。
我们把这个数与原数异或，就会造成：第一个1以后的数（包括第一个1）全部取1.其他的位全部取0.即构成一个由一堆0后面跟一堆1的串。
那么再把原式做一个与运算，那么除了原来的那个1（对应位都是1）为1，其他位全是0，完成任务。
现在来解释第二个，依旧拿(6)10举例子
根据计算机的补码的性质，补码等于原码的反码+1
-x = ~x + 1
例子：
x = (9)10 = 0 1001
-x = 1 0110 + 1 = 1 0111
再做与操作，得0 0001，这样就得到第一个1
用lowbit运算统计1的个数
我们可以使用lowbit运算统计一个整数的二进制形式下1的个数。
实现原理很简单啦，就是：我们先用lowbit运算找出lowbit(x)，然后用原数减去这个数，依次循环，直到为0为止。
这也是树状数组的实现原理。
#include
using namespace std;
int lowbit(int x){
return x & -x;
//-x = ~x + 1 //(x取反加1)
}
int main(){
int n;
cin >> n;
while(n --){
int x;
cin >> x;
int res = 0;
while(x) {
x -= lowbit(x);
res ++;
}
cout << res << " ";
}
return 0;
}
lowbit运算的应用
关于lowbit运算，最著名的应用应该算是树状数组。但是lowbit的神妙远远不止树状数组，在很多二进制和位运算的相关题目中，都有lowbit运算的影子。甚至，在状态压缩DP中，lowbit也扮演着一份不可忽视的角色。