关于位运算:lowbit的原理和应用

家喻户晓，lowbit 是为了获取一个数的二进制中最低位的 1 对应的值，比方 lowbit(10) = 10，因为 10 的二进制表白是 1010。

lowbit 的实现

lowbit 有两种实现形式：

1. x & (x ^ (x – 1))
   以二进制数 x = 11110000 为例，x – 1=11101111，容易发现，其实就是将 x 的最初一个 1 变为 0，再将前面的 0 都变成 1，这样以来，再与 x 做异或：
   11110000 ^
   11101111
   后果是 00011111。也就是把原数 x 最初一个 1 以及前面的 0 都变成 1，把最初一个 1 后面的 1 都变成 0。既然后面都是零了，那么只有和原数 x 做和的操作，即可将异或的后果最初一个 1 前面的 1 都变成 0，也就是
   11110000 &
   00011111
   失去 00010000，这样就优雅得失去了最初一个 1 示意的数，也就是原数 x 的最大的能够整除的数。这里 x 的十进制是 240，lowbit 的后果是 16=2^4。
2. x & -x
   这种算法其实是利用了计算机的补码性质。计算机为了示意正数，将对应的负数二进制全副取反再加一。
   以 x =11010000 为例，-x=00101111 + 1 = 00110000，能够看到，取反加一后原数最初一个 1 前面的所有 0 还是 0（因为加法的进位操作），原数最初一个 1 前的所有 1 都变成了 0，而所有 0 都变成了 1，其实次要外围就是将最初一个 1 后面的数都翻转，这样再与原数进行或操作，最初一个 1 后面都会是 0，也就是
   11010000 &
   00110000
   后果是 00010000。

lowbit 的利用

1. 统计二进制下 1 的个数
   先用原数计算出 lowbit(x)，而后用原数减去这个数，再一直 lowbit。

int ans = 0;
while(x > 0)
{
    x -= x & -x;
    ans++;
}

这也是树状数组的实现原理。
基于这个操作咱们能够将合成出一个整数能够由哪些的 2 的幂相加形成。比方 11110000 也就是 240=2^4+2^5+2^6+2^7。

参考：

1. https://www.jianshu.com/p/6c3…
2. https://blog.csdn.net/qq_4172…
3. https://www.cnblogs.com/fusiw…