lowbit 与 highbit
lowbit
lowbit 在竞赛中还是很常见的，比如树状数组就必须要用 lowbit。
lowbit 的原理是利用原码, 反码, 补码的性质来获得数字在二进制下最低位的 \(1\)。理解了原码，反码，补码，就不难理解 lowbit 了。
lowbit 代码如下：
inline int lowbit(int x) {
return x & -x;
}
以一个例子来理解上面的代码（假设你已经理解了原码，反码，补码）：
- 我们假设 \(n = 8\)。\(8\) 的二进制为 ： \(00001000\)。
- 对 \(8\) 取反的二进制为：\(11110111\)。
- 再对取反 \(8\) 加一（补码）的二进制为：\(11111000\)。
- 进行与操作之后：\(00001000\)。
就得到了我们的 \(lowbit(8) = 8\)
highbit
这个相对来说要少见些。
顾名思义，它干的事与 lowbit 相反，求的是数字在二进制下最高位的 \(1\)。
其原理是将一个数二进制下最高位的 \(1\) 及其右面的每一位都补充为 \(1\)，然后把最高位右面的都减掉，剩下就是最高位的 \(1\)。代码如下：
int highbit(int x){
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x - (x >> 1);
}
为什么这样写呢？
我们假设 \(x\) 在二进制下只有最高位是 \(1\)，其余位都是 \(0\)。通过 highbit 函数的第一行，我们通过右移 \(1\) 位并与原来的 \(x\) 异或，将 \(x\) 最高位往右一位填充为了 \(1\)，现在总共有连续的两个 \(1\)。接着通过第二行，可以继续向右填充两位，现在统共有 \(4\) 位 \(1\) 了。接下来的代码以此类推，我们就可以把右面全部填充为 \(1\) 了，最后 x - (x >> 1) 就可以得到我们想要的 highbit 了。
推广一下，如果最高位右面还有 \(1\)，上面的代码依旧是正确的。
上面的函数返回值是 int 型的，如果用别的类型，可以自行调整右移位数。