1. 首页
  2. IT资讯

二进制究竟有什么用?齐姐带你看看那些好玩儿的「位操作」

本篇终于讲到了齐姐文章里常常出现的分割线!

计算机说到底就是 0 和 1,所有的数在内存中都是以二进制的形式储存的。

而位操作,或者说位运算,就是直接对内存中的二进制位进行操作。

位运算可以说是我们的基本功,今天这篇文章就从以下角度和大家一起玩转位运算。

  1. 二进制究竟有什么用?
  2. 原码 反码 补码
  3. 7 种位运算

当然了,位运算还有很多奇技淫巧,如果大家还想看进阶篇,记得给我点赞或者留言告诉我哦~

二进制的作用

在实际生产中,二进制是用来优化时间和空间的。

二进制的运算,可能并不会降低复杂度的等级,但是可以把复杂度前面的系数降下来。

举个例子。

大家都知道堆,或者叫优先队列,一般来说是用完全二叉树来实现的,叫做二叉堆

最小堆

最小堆

二叉堆插入、删除元素的时间复杂度都是 O(logn),如果这个不清楚的同学赶紧在公众号内回复「」复习一下,或者点击这里

但是有另一种堆,它能够做到 O(1) 的时间插入元素,O(logn) 的时间删除元素,我在堆这篇文章里也提到过,就是斐波那契堆

但为什么不用呢?

就是因为 O(1) 前面的系数非常大。

二进制究竟有什么用?齐姐带你看看那些好玩儿的「位操作」

我们说 O(logn) 比 O(1) 好,是有个条件的,那就是 n 非常非常大的情况下,但是实际上,如果 n 是在 int 范围内,那么取个 log 也不过就是 32 了,反而这个 O(1) 的时间复杂度可能系数达到几百几千。

一般来说实际应用中时间的测量并不是时间复杂度这么简单,有的时候就需要你把两个算法都实现出来,去跑去测量它的时间,才能决定哪个好。

那么二进制一次能够作用于 32 位上(假设是一个 int),如果数据表示的巧妙,这完全可以优化 32 倍,多用几个 int 就多优化了好几个 32 倍,不香吗?

二进制究竟有什么用?齐姐带你看看那些好玩儿的「位操作」

除了优化时间,还可以优化空间。

比如在网站发布新版本时,一般都会附上支持该版本的浏览器列表,不然有些老掉牙的浏览器看不到我的新功能还算我的锅么?

那么怎么有效的表示这个浏览器列表呢?

全世界所有浏览器都有个国际标准编号,这里我就简单假设一下:

  • 0 表示 QQ 浏览器
  • 1 表示 Chrome 浏览器
  • 2 表示火狐浏览器
  • 3 表示 …

那么我们就可以用一个 int 表示是否支持 32 个浏览器的状态,如果这个浏览器能用,那么这一位上就设为 1,那么比如国内的某个网站可以表示为:

  • 0b …. 1101

所以位操作在很多代码里都很常用,比如网络协议、操作系统等等。

接下来我们说说具体的知识点。

原码 反码 补码

数字有正有负,Java 中用的是 signed type,就是有正有负的。

虽然在 Java 8 之后,也用了个工具来实现 unsigned type,但是其实底层实现是没有的。

二进制最左边的一位是符号位,

  • 0 表示这个数是非负数;
  • 1 表示这个数是负数。

对了,最左边的一位英文叫做 most significant bit,好多同学面试说的五花八门。。。

正数

正数的原码反码补码相同,没啥好说的。

比如:

  • int 1 = 0b 0000 0000 0000 0001
  • int 2 = 0b 0000 0000 0000 0010

负数:

原码:把相应的正数的符号位设为 1。

  • -1 的原码 = 0b 1000 0000 0000 0001
  • -2 的原码 = 0b 1000 0000 0000 0010

反码 ones’ complement:符号位是 1,其余位取反。

  • -1 的反码 = 0b 1111 1111 1111 1110
  • -2 的反码 = 0b 1111 1111 1111 1101

补码 two’s complement :反码 + 1。

  • -1 的补码 = 0b 1111 1111 1111 1111
  • -2 的补码 = 0b 1111 1111 1111 1110

而计算机中真正用来存储数据的是用补码

这里稍微注意下反码和补码的英文,ones' 的这个 ' 在后面,two's 的这个 ' 在中间。。

为什么计算机要用补码来存储数据呢?

可能有同学会说正零负零的原因,但这只是表面现象。

实际上通过补码这样精巧的设计,计算机做加减乘除运算就不用考虑符号,就可以让硬件里 CPU 的设计变得异常简单。

最初计算机只有加法器没有减法器,所以它用这么一种方式用加法完成了减法。

int 的最大值是多少?

正是因为最左边一位是符号位,所以正数的表示就少了一位能用的,那么 int 的最大值就是:

0111111…11 (31 ones) = 2^31 – 1 = 2147483647

7