理解二进制操作

更新日期: 2019-10-11阅读: 1.7k标签: 进制

引言

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


移位操作

负数的二进制

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

正数表示很简单, 从右往左 ,各个二进制位上的 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
或 1
异或 1
与 1
或 0

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

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

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


代码里的二进制

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

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

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

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


小结

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

原文 https://zhenbianshu.github.io/2019/10/understand_binary_operation.html


链接: https://www.fly63.com/article/detial/6369

二进制和十进制相互转换、位移运算

自己的解题思路是将十进制的数转为二进制(不足32位补0),然后依次取8位转化为十进制的数字,再用.连接即为IP。里面的几个点记录一下:十进制转换为二进制 numObj.toString([radix]) radix可以指定进制

Js进制转换

参数radix支持 [2, 36] 之间的整数。例如:参数值为2,则表示二进制;为8,则表示八进制;为16,则表示十六进制。如果省略参数radix,则默认为10(十进制)。

js 进制转换/进制编码解码

js 进制转换支持 2-36 , 即 0-9a-z .可以用于混淆、数值缩短、特殊符号转换…字符串36进制编码解码;ip地址端口号36进制编码解码

Js将十进制转换为十六进制?

JavaScript中有很多内置函数可以帮我们进行数(进)制转换。那么给定一个十进制数字,如何将数字从十进制转换为十六进制?下面本篇文章就来给大家介绍一个使用JavaScript将十进制转换为十六进制的方法

JavaScript 进制转换&位运算

在一般的代码中很少会接触到进制和位运算,但这不代表我们可以不去学习它。作为一位编程人员,这些都是基础知识。如果你没有学过这方面的知识,也不要慌,接下来的知识并不会很难。本文你将会学习到:进制转换,按位操作符,Javascript进制转换

nodejs怎么存取2进制数据?

在客户端javascript脚本代码中,对于二进制数据并没有提供一个很好的支持。然后在nodejs中需要处理像TCP流或文件流时,必须要处理二进制数据。因此在node.js中,定义了一个Buffer类,该类用来创建一个专门存放二进制数据的缓存区

十进制与十六进制之间的转换

将十进制数 x 除以 16, 即 x = q * 16 + r,取得余数 r 和 商 q,此时余数 r 就是 x 用十六进制表示时的最低位值; 之后商值 q 继续进行以上的除法操作, 获取每次的余数 r 作为 十六进制表示时的低位值, 直到 q 值小于 16 为值, 此时的

二进制数与位运算符

位运算符是基于二级制数进行操作的,即表示数字的 32 个数位,它由0和1组成…ECMAScript整数有两种类型,即有符号整数(允许用正数和负数)和无符号整数(只允许用正数)

JavaScript中的多种进制与进制转换

JavaScript 中提供的进制表示方法有四种:十进制、二进制、十六进制、八进制。对于数值字面量,主要使用不同的前缀来区分:

Js二进制家族:文件base64、File、Blob、ArrayBuffer互转

JavaScript 提供了一些 API 来处理文件或原始文件数据,例如:File、Blob、FileReader、ArrayBuffer、base64 等。Blob 全称为 binary large object ,即二进制大对象,它是 JavaScript 中的一个对象

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!