Oct 27, 2019 - 理解二进制操作

2787 Word Count

最近在用 shell 写一个小工具，里面要用到复杂的二进制操作，对 int 值进行位操作和与或非，而 shell 的语法里，& 是取布尔与，>> 是重定向，不支持二进制操作，为了写出只需要默认系统环境就可以运行的程序，于是只好摸出了好久不用的 C。在使用 C 实现二进制操作的过程中，对二进制的操作有了新的理解。

当然本文并不是要讲 C 语言的语法，而是对二进制操作符的梳理和代码里常用二进制操作的总结。

转载随意，文章会持续修订，请注明来源地址：https://zhenbianshu.github.io 。

负数的二进制

在了解移位操作之前，我们先来复习一下计算机的二进制表示形式。

正数表示很简单，从右往左，各个二进制位上的 1 分别代表 2^(n-1)，将这些二进制位上的 1 代表的值相加，结果就是这个数的十进制结果。

而负数是以补码的形式表示，原码的计算方式：

1. 获取到负数绝对值的二进制表示方式作为原码；
2. 将原码各位取反得到反码；
3. 将反码再加 1 得到补码；

-2 原码： 00000000 00000000 000000000 00000010
-2 反码： 11111111 11111111 11111111 11111101
-2 补码： 11111111 11111111 11111111 11111110

算术移位和逻辑移位

正是负数的特殊表示形式，产生了移位方式的差异。二进制移位操作，按移位方式可以分为算术移位和逻辑移位。

• 逻辑移位就像我们在处理一个二进制字符串，不管往哪个方向移动，移动方向上溢出的位都舍弃，空位补 0。
• 而算术移位就像进行算术运算，向左移 n 位的结果就等于乘 2 的 n 次方，而向右移 n 位结果就等于除以 2 的 n 次方。从结果二进制字符串上来看，算术左右与逻辑左移的结果相同，算术右移的补位方式不同于逻辑右移统一在左边补 0，而是补充符号位。

可以看到， -2 的补码最左边的符合位是 1，如果对它进行逻辑左移 1 位，左边溢出的 1 被舍弃，右边补上 0，移位之后结果是 -4，它还是一个负数。 但如果对 -2 进行逻辑右移 1 位，左边右边的 0 被舍弃掉，左边的符号位以 0 补充，它就变成了正的 2^31，这可能就背离了我们的初衷。针对这种情况就产生了复杂的算术右移。

逻辑右移 C 实现

Java 里的右移操作符默认是对数字进行算术右移，当然为了满足正常的逻辑右移，Java 还提供了 >>> 操作符。C 里面也是如此，而想实现逻辑右移就只能自己动手了。

对比逻辑右移和算术右移不难发现，算术右移的问题在于负数时会保留符号位，正数向右移动时，左侧补充 0，而负数向右移动 n 位，左侧就会补充 n 个 1，如果将这 n 个 1 换成 0，也就完成了算术右移到逻辑右移的转变。

所以要进行逻辑右移，我们要先使用 掩码 来保存左侧补充的符号位，我们将它定义为左侧 n 位都为 0，其余位都为 1 的二进制数，使用它和算术右移的结果作 与运算，这样，逻辑右移后左侧补充的 n 个 1 都会被置为 0 ，而右侧 与 1 ，结果与原来相同。

写出来的代码如下：

int logic_r_shift(int x, int n) {
    int mask = ~(1 << 31 >> (n - 1));
    return (x >> n) & mask;
}

整体思想是：

1. 通过 1<<31 溢出后产生一个最高位是 1，其他位是 0 的数字；
2. 然后再将其算术右移 n-1 位，产生一个高 n 位全是 1，低位全是 0 的数字；
3. 对生成的数字各位取反，产生一个高 n 位是 0，低位全是 1 的掩码；
4. 将掩码与算术右移产生的结果进行与运算，由符号位移动在高 n 位补的 1 与 掩码高位的 0 后被清除，低位与掩码低位的 1 保持不变。

二进制运算符

除了移位操作符外，一般语言还会提供一些二进制运算符，常见的 &(与)、|(或)、~(非)、^(异或)，使用这些运算符，我们就可以操作二进制数中的某一个二进制位。

常见的操作方式有：

• 清零，与 0，任何位与 0 后结果一定是 0。
• 置一 或 1，任何位或 1 后结果一定是 1。
• 取反，异或 1，异或在两个位不同时会返回 1，如果原来位是 1，则会返回 0，如果原来位是 0，则会返回 1。
• 判断某位的值，与 1，1 与 1 结果是 1，而 0 与 1 结果是 0。
• 值保持不变，或 0，任何位或 0，结果还会是原来的值。

这些操作方式一般并不能直接使用，而是需要多个操作组合起来，很多时候还要借用移位操作符的能力。

主要思想是：先确定要操作的二进制位的位置，再对常见的二进制数如（1、-1）进行移位操作产生对应的掩码，这些掩码的各个二进制位上应该分别保留着上面各种能力，最后将掩码与要操作的数进行运算。

当然，这种 “制作” 掩码的能力需要多次训练，这也就要求我们在代码中多观察和应用二进制操作。

代码里的二进制

我们经常在各种面试题的解法里看到二进制操作，可能会以为非常高级的设计才需要用到它，其实并不然，二进制操作符也是我们写代码过程中常见的符号，也可以应用于我们的普通代码内。

举一些我们经常能见到的例子：

• HashMap 里容器容量的表示，就使用 1 右移 N 位来表达，这是因为 HashMap 的扩容倍数是 2，将容量左移一位即可。在乘除法上，移位操作的效率要比普通的算术运算符高太多。
• 线程池 ThreadPoolExecutor 的 ctl 字段上，在一个 integer 上同时存储了线程池的运行状态（高三位）和线程数（低 29 位）。把这些信息同时存在同一个字段，搭配上 CAS 操作，即可保证 ctl 字段的隔离性和数据一致性。
• 各种编码类，如 Base64、Crc32 等，这些类对二进制的应用，不同于上面提到的两种类，它们对二进制字符的操作，算术运算符根本无法替代。

当然，我们也可以在业务代码里应用二进制操作，比如使用一个 integer 值存储多个返回码，不光提升传输效率，还能有一定的加密作用，当然了，前提要求服务提供方和消费方制定好确定的协议。

二进制的操作还是有违于我们从小到大的算术直觉的，这可能是我们理解二进制操作的难点，不过我相信，只要用心观察，勤于练习，灵活运用二进制操作也不是难事。

关于本文有什么疑问可以在下面留言交流，如果您觉得本文对您有帮助，欢迎关注我的 微博 或 GitHub 。您也可以在我的 博客REPO 右上角点击 Watch 并选择 Releases only 项来 订阅 我的博客，有新文章发布会第一时间通知您。