对于 x & (-x) 的理解以及常用的位运算整理

这题涉及到对最低比特位的操作，周赛结束后看题解，发现我的思路是没有问题的，但是在代码实现上磕磕绊绊，归根结底是对位操作的掌握不够，看大佬们的题解中对 lowbit 的实现都是x & (-x)，遂在此记录一下对于x & (-x)的理解以及其它常用的位运算。

x & (-x)

-x 在计算机中是以 x 的补码形式存储的，计算方式是对 x 按位取反后加 1，即(~x)+1，也就是说x & (-x) == x & (~x + 1)。

那么，对于整数运算 x & (-x)有：

当 x 为 0 时，即 0 & 0，结果为 0。
当 x 为奇数时，最后一个比特位为 1，取反后变成 0，加 1 后不产生进位，对前面的位不产生影响，因此 x 和-x 除了最后一位外，前面的位相反，按位进行与操作后结果均为 0，最后一位是 1&1，结果为 1。即 x 为奇数时，x & (-x) = 1。
当 x 为偶数时，分两种情况讨论：
- 当 x 为偶数且为 2 的 m 次方时，x 的二进制表示中，只有从右往左的第 m+1 位值是 1，其余位均为 0，第 m+1 位右边有 m 位 0，x 取反加 1 后，从右到左一直到第 m 位，是 m 个 0，第 m+1 位及其左边全是 1。即，x & (-x) = x 。
- 当 x 为偶数，但不等于 2 的 m 次方时，可以写作。其中，y 的最低位为 1。本质上就是把 x 用一个奇数左移 k 位来表示。此时 x 的二进制表示中，从右往左第 k+1 位为 1，右边有 k 个 0。当对 x 取反时，最右边的 k 位 0 变成 1，第 k+1 位变为 0；再加 1，最右边的 k 位就又变成了 0，第 k+1 位因为进位的关系变成了 1。第 k+1 位左边的位因为没有进位，正好和 x 原来对应的位上的值相反。二者按位与后得到第 k+1 位上为 1，其余位都为 0，结果为。

总结：x & (-x)常用于 lowbit 的实现（树状数组），lowbit 的定义是：x & (-x)，当x为 0 时结果为 0；x为奇数时，结果为 1；x为偶数时，结果为x中最大的 2 次方因子。

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

x & (-x)：保留 x 的二进制表达式中最低位的 1，其余位置 0（即 x 最大的 2 次方因子）
x & (x-1)：消除 x 的二进制表达式中最低位的 1，其余保持不变（可以判断 x 是否为 2 的幂次）
(x>>i) & 1 或者 x & (1<<i)：获取 x 的二进制表达式中的第 i 位数字，最常用的是取二进制下的最末位，即x & 1，用于判断奇偶
x = x|(1<<i)：设置第 i 位为 1
x = x & (~(1<<i))：设置第 i 位为 0
x = x ^ (1<<i)：将第 i 位取反

按位反（~）> 位移运算（<<, >>）> 按位与（&）> 按位异或（^）> 按位或（|）