lowbit()

lowbit()

简介：众所周知，lowbit()操作是算法竞赛中的高级技巧，特别是高级数据结构，线段树的核心，还有什么二进制与位运算题目，而本文就用最通俗易懂的话，来教会大家lowbit的含义。

含义：lowbit(x)是x的二进制表达式中最低位的1所对应的值。

什么意思了：

十进制 二进制 最低位的1所对应的值对应的二进制数 最低位的1所对应的值对应的十进制数

1 1 1 1

2 10 10 2

111 1 1 4 100 100 4

5 101 1 1

6 110 10 2

7 111 1 1

方法：我们得到lowbit的值，只需要得到最后一个1的位置，并且把除了这个位置之外的所有位置全部置成零。然后输出就可以。

先上代码：

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

这个代码实在是很简单，就是一个数与它的负数进行与运算。

我们希望获得一个数的最低位的1所对应值，那么就需要将这个数字与自己的补码取与，那么计算机中一个数的补码是啥了，没错就是这个数字的负数(负数就是正数的反码+1)，

为啥和补码去与就可以了：

（110）2 = 6 原码

（001）2 反码

（010）2 补码

可以发现变为反码后 x 与反码数字位每一位都不同， 所以当反码加1，成为补码的时候，反码会逢1一直进位直到遇到0，且这个0变成了1，然后就寻到了，第一个不为0的1的位置，而且这个1前面的数字，全部变成了0.