lowbit理解

我们在树状数组中可以遇到lowbit这个函数，他的用处是找最低位1的，一般写成(x & -x)形式。

原理

我们知道在计算机中二进制是以补码存储的。
对于x(x>0),我们知道他的补码就是他的本身，但-x怎么求呢
对于整数x, $[x{]}_{补}=2^{n+1}-\mid x\mid$[x]补​=2n+1−∣x∣,n为x的二进制最高位
设 $x=26,[x{]}_{补}=011010(B)$x=26,[x]补​=011010(B)
$-x=-26,[-x{]}_{补}=2^5-26=100000-011010=100110(B)$−x=−26,[−x]补​=25−26=100000−011010=100110(B),最高位为符号位
我们可以发现 $[-x{]}_{补}$[−x]补​为 $[x{]}_{补}$[x]补​连同符号位取反加一之后的结果
由上知 $\left[x{]}_{补}\mathrm{\&}\right[-x{]}_{补}=10\left(B\right)$[x]补​&[−x]补​=10(B),发现结果恰好就是最低位1