位运算的“奇淫技巧”
本文最后更新于：2023年12月17日 下午
前言
介绍一些位运算的技巧，比如对应计算一个二进制整数中 1 bit的个数，不是通过循环遍历每一bit 是否为1，而是可以选择一些 tricky 的位运算来完成。
先来介绍一下本文中所使用的一些位运算操作符。
1 | |
在这篇文章中，表示的数字均为 8 bit 有符号整数（但是上述这些操作是可以在任意长度的有符号整数上执行的），并用 ‘x’ 来表示，而位运算计算后的结果用 ‘y’ 来表示。 其中 ‘x’ 的每一bit，使用 b7, b6, b5, b4, b3, b2, b1, b0 来表示，b7 是权重最高位（在符号数里就是符号位），b0 是权重最小的位。
接下来会先基本的bit hacks 介绍，然后逐渐深入到更高效的方法。
1. 检验一个整数的奇偶性
1 | |
相信很多人都已经看到过上述的技巧，其最基本的思想就是如果一个整数是奇数，那么它的最低位 b0 就为1。通过 将 ‘x’ 和 1 进行 AND-ing 操作，忽略其他bits，只关注 b0 即可，如果结果为0 表示 ‘x’ 是偶数，结果为1 表示 ‘x’ 是奇数。
举个例子，比如数字43，二进制表示为00101011，通过与 1 进行 AND-ing 操作，清除更高位的数值而只保留 b0 ，最终剩余结果为 1 就表示整数为奇数。
1 | |
再举一个偶数的例子98，其二进制表示为1100010。在 AND-ing 操作后，最终结果为0，因此98是一个偶数。
1 | |
2. 检验第n位 bit 是否置1
1 | |
在先前的第一个例子，我们看到了通过 （x & 1）来检验第一位 b0 是否置1，这个技巧可以通过改善实现检验第n位是否置1。主要做法就是将 1 左移n个位置，然后做相同的AND 操作，将除了第n位的其他bits清0。
下面演示了当你将 1 左移不同位数的结果：
1 | |
现在，我们将 ‘x’ 与 左移n位的 数字1 进行 AND 操作，就可以保留 ‘x’上第n位bit （对于 b0 来说是第0位）而将其他bit 清零。所以如果最终结果为0，表明对应bit 是0，最终结果不为0，表明对应bit置为1。
接下来给出一些例子，比如说 122 的第3rd bit 是否置为1，我们可以通过122 & (1<<3)来实现，具体来说如下所示：
1 | |
可以看到最终结果不为0，因此122 对应的 3rd bit 是置为1的。
注意：在本文中，bit 的位数下标从0开始，也就是第0位bit，第1位bit ，…， 第7位 bit。
3. 将第n位 bit 置 1
1 | |
这个 bit hack 结合了左移 (1<<n) 和 OR 运算的技巧，y = x | (1<<n)通过和一个第n位 置1 的数值进行 OR 运算就可以使得 ‘x’ 的第n位 置1。因为和 0 进行 OR-ing 数值保持不变，和 1 进行 OR-ing 对应bit变为1（如果不是1的话）。
同样给出一个例子，对于数120，我们希望将其 2nd bit 置为1，如下所示
1 | |
4. 将第n位 bit 置 0
1 | |
这个bit hack 主要通过y = x & ~(1<<n)实现，~(1<<n)起到的作用是将除了第n位置0，其余位置1，比如下面这样：
1 | |
再通过 AND-ing 操作，就可以使得将 ‘x’ 的第n位置0，因为 AND-ing 中有个 bit 为0，结果 bit 就为0。下面给出数127，将第4位 bit 置0的例子：
1 | |
5. 反转第n位 bit
1 | |
这个bit hack 主要实现方式为y = x ^ (1<<n)，结合了左移和XOR 运算。(1<<n)将对应的第n位置1，而通过 XOR 运算，如果 ‘x’ 第n位为0，就会变为1，如果第n位为1，就会变为0，从而实现反转的效果。
下面给出一个例子，将 01110101 的第5位进行反转：
1 | |
6. 将最右边的1-bit置为0
1 | |
该方式主要通过y = x & (x-1)来实现。比如对于一个整数 00101010（最右边的1用黑体标出），当将最后边的1-bit置为0后，就变成了00101000（对应位变成了0）。
这里给出更多的例子：
1 | |
这是如何实现的呢，主要有两个可能的场景：
- 该整数值存在一个最右边的1-bit。在这种情况下，当该数值减去1后，会将该二进制数的最右边的1-bit置为0，同时其右边所有低位的0变成1（就是一个减法得到的结果）。这个减法操作得到的结果，相当于已经把最右边的1-bit置0，然后再通过和原始值进行AND-ing 操作，就可以把低位的1都置为0。
- 当该二进制数不存在一个最右边的 1-bit（全为0）。那么在这种情况下，减1后会下溢，即所有 bit 置为 1 ，那么再和原始值（全0）进行AND-ing操作得到的也还是0。
7. 只保留最右边的 1-bit
y = x & (-x)
该方法通过y = x & (-x)实现，将只保留 x 的最右边的 1-bit ，把其他位都置为0。比如对于 01010100 (最右侧 1 用黑体标出)，得到的结果为 00000100。
这里再给出更多的例子：
1 | |
接下来探讨其实现原理。主要就是依赖于在计算机中， -x （对应的负数）跟 ~x+1 （按位取反后加1） 是一样的。
不妨设 x 最右边的 1-bit 为bi，以下标 i 为界，将 bi 左侧的 bits 位设为 bi+1, …, bn，将 bi 右侧的所有 bits 位设为 bi-1, bi-2 , … , b0 （位于右侧的全为 0 ，因为 bi 是最右侧的 1 ）。
现在当我计算 -x ，首先做取反操作 x ，也就是将 bi~ 置为0， bi-1…b0 都置为 1，将 bi+1 … bn 等位进行反转。然后做加 1 操作。因为 bi-1…b0 都为1，所以加 1 后会想 bi 进位（因为 bi 是第一个 0 bit ）。
此时我们不难发现，对于 -x ，bi+1 … bn 等位反转了， bi 依然保持不变，bi-1…b0 也依然全为 0 。所以现在将 x 与 -x 进行 AND-ing 操作，就可以使得 bi+1 … bn 置为 0 ，bi 保持 1， bi-1…b0 也全为 0 。只有一个 bit 保留了下来，就是最右边的 1-bit 。
8. 将最右边 1-bit 右侧的所有低位 bit 置 1
y = x | (x-1)
具体实现就是 y = x | (x-1) 。这个翻译过来有点拗口，给个例子就能理解了，给出数 01010000 ，执行后就得到 01011111，原来最右边 1-bit 右边的低位都置为1 。接下来看更多的一些例子。
1 | |
这个方法的实现原理跟方法6很像，所以这里就不再证明了。
9. 保留最右边的 0-bit
y = ~x & (x+1)
该方法的实现为y = ~x & (x+1) 。该方法与方法7正好相反，它是找到最右侧的 0-bit，将其他位都置为0，将该 bit 置为 1 。距离来说，给定数 10101011，经过处理后的结果为，00000100。再给出更多的例子：
1 | |
接下来给出证明。与之前类似，不妨设最右边的 0-bit 设置为 bi ，将 bi 左侧的 bits 位设为 bi+1, …, bn，将 bi 右侧的所有 bits 位设为 bi-1, bi-2 , … , b0 （位于右侧的全为 1 ，因为 bi 是最右侧的 0 ）。
那么对于 x 来说，将所有位进行反转，包括最右侧的 0-bit，bi~ 也从 0 变成了 1 。
对于 x+1 来说，因为 bi-1, bi-2 , … , b0 全为1，加 1 之后会向 bi 进位，因此 bi 也变成了 1，bi-1, bi-2 , … , b0 都变成了0，而高位 bi+1, …, bn 保持不变。
此时再将 x 与 x+1 进行 AND-ing 操作，就只有 bi~ 位保留下来，其他位均为 0 。
10. 将最右侧的 0-bit 置为1
y = x | (x+1)
该方法实现为 `y = x | (x+1)`。主要就是将最右侧的 0-bit 置为1，例如对于数 10100**0**11 经过运算后，得到结果 10100**1**11。给出更多的例子：1 | |
正确性也非常好理解。x+1 的操作将原来 x 的最右侧的 0-bit， bi 置为1，bi-1, bi-2 , … , b0 都变成了0，而高位 bi+1, …, bn 保持不变。此时再和 x 做 OR-ing 运算，就可以使得原来 x 的最右侧 0-bit bi 置为 1。
Bonus
一个简单的C语言函数，实现打印一个数字的低8位。
1 | |