位运算

取出整数 \(n\) 在二进制下的最后一位：

直接说结论：n & 1。这一点可以用来判奇偶性，也是其它二进制操作中很重要的一点。

取出整数 \(n\) 在二进制下的第 \(k\) 位：

注：二进制位从 \(0\) 开始计。

因为我们要取第 \(k\) 位，所以 \(0 \sim k - 1\) 位不用考虑，直接右移 \(k\) 位。

此时 \(n\) 末尾即为第 \(k\) 位，要取它，只需要取 \(n\) 的最后一位即可，所以是 (n >> k) & 1。

把 \(n\) 的第 \(k\) 位取反：

谈到取反，不难想到异或。任何位异或 \(0\) 不变，异或 \(1\) 取反，所以即为 n ^ (1 << k)。

把 \(n\) 的第 \(k\) 位变为 \(1\)：

不难发现，把上述方法的异或改成或即可，即 n | (1 << k)。

把 \(n\) 的第 \(k\) 位变为 \(1\)：

把任意位变为零很容易想到与。其它位都与上 \(1\)，第 \(k\) 位与上 \(0\)，所以是 \(n & (~(1 << k))\)。

\(\operatorname{lowbit}\) 函数：

\(\operatorname{lowbit}(n)\) 的意思是，设 \(n\) 最低位为 \(k\)，那么 \(\operatorname{lowbit}(n) = 2 ^ k\)。

如何推导 \(\operatorname{lowbit}\) 函数的公式呢？首先，第 \(k\) 位后所有的数肯定都是 \(0\)，那么将 \(n\) 取反后，末尾的所有数都会变成 \(1\)，第 \(k\) 位会变成 \(0\)。那么将 \(n\) 取反后再加 \(1\)，第 \(k\) 位后所有的数又会变成 \(0\)，第 \(k\) 位又会变成 \(1\)，其它位都全部取反。这时将现在的 \(n\) 和原来的 \(n\) 按位与，就只会保留第 \(k\) 位和后面的 \(0\)，这就是我们想要的 \(\operatorname{lowbit}(n)\)。而这里所说的 现在的\(n\)，就是在计算机反码下的 \(-n\)。所以答案为 lowbit(n) = n & (-n)。

\(\operatorname{popcount}\) 函数：

\(\operatorname{popcount}(n)\) 是 \(n\) 在二进制下有多少个 \(1\) ，方法即为每次将 \(n\) 减去 \(\operatorname{lowbit}(n)\)，在将答案加 \(1\)。