数据结构：深入二进制的世界

数据结构：深入二进制的世界

正式开始

本章从数据结构开始盘它，先小尝一下数据结构的内容。

算法和数据结构

算法无处不在，区别在于烂算法和牛逼的算法

公司有算法团队的，没打过交道也不知道是干什么的，应该是很牛逼的样子

但是，换个思路来想，使用算法和不使用算法本质上都是为了解决某个问题，那么我们是不是可以这么理解算法：

对具体的问题，设计出一套解决这个问题的具体流程，这个流程我们就可以将其称之为算法

不过在处理问题的过程中，通过可量化的指标来衡量我们设计的这个算法的好坏，比如说：执行效率，时间复杂度等等

这样来想的话，算法也并没有那么神秘。

而与之相配合的是数据结构，从百科中找到这样的介绍

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率

所以说，牛逼的算法不一定牛逼，有可能是数据结构选的好

二进制表示形式

在聊之前，先统计下有多少猿会打印出一个整数的二进制表示形式？ 3s中时间考虑！！！

公布程序

// 打印整数的二进制表示形式  public static void printInt32(int num) {      for (int i = 31; i >= 0; i--) {          System.out.print((num & (1 << i)) == 0 ? "0" : "1");     }      System.out.println();  }  ​  // 将二进制表示形式还原为整数  public static void printToInt(String s) {      // 该方法仅限正数      System.out.println(Integer.parseInt(s, 2));  }

那我们都知道，int类型在Java中占4个字节32位，那么通过上面的方式就可以表示出整个int类型的32位表现形式

其中

最左侧一位是最高位，表示符号位： 最高位如果是0，表示该数为正数 最高位如果是1，表示该数为负数

printInt32(Integer.MAX_VALUE); // 01111111111111111111111111111111  printInt32(0); // 00000000000000000000000000000000  printInt32(-1); // 11111111111111111111111111111111  printInt32(Integer.MIN_VALUE); // 10000000000000000000000000000000

扩展： 因为将0也分到了正数中，所以在正数范围是0~231-1， 而负数的范围是-1~231

进制转换

想要不借助程序将一个整数转换为二进制表示，我们可以采用除2得余法，用实际例子表示

我们现在要计算17的二进制表示

要将二进制再转换为十进制的话，就要采用*全部位2(n-1)**

10001 = 1*24 + 0 + 0 + 1*20 = 16 + 1 = 17

当然，如果出现小数的话，那么就要分开计算：

整数位采用除2得余法，取余数逆序排列 小数位采用*小数2**，然后取整数部分顺序排列

至于为什么是这种情况，在聊到之前我们先来介绍三个基本概念

原码，补码，反码

虽然我们上层在定义类型的时候采用的是int，long之类的，但是计算机在整体处理的时候都会将其转换成二进制表现形式，我们也可以将其称之为机器数

机器数是带符号的，和上面的规则一样

而机器数的第一位是符号位，后边才是真正的数值，所以机器数的形式值就不等于真正的数值。于是为了区分将带符号位的机器数对应的真正数值称为机器数的真值

而我们所说的原码就是符号位+|真值|：正数添0，负数添1

比如：1和-1

1原码 = 00000000000000000000000000000001 -1原码 = 10000000000000000000000000000001 需要注意：原码不会真正参与计算，至于为什么后面我们会介绍到

而反码的展示分为两种情况

如果为正数的话，那么反码就是原码本身 如果为负数的话，那么就将原码除符号位外，其余位全部取反

1 = [00000000000000000000000000000001]原码 = [00000000000000000000000000000001]反码 -1 = [10000000000000000000000000000001]原码 = [11111111111111111111111111111110]反码

补码是同样的道理

如果为正数的话，补码就是原码本身 如果是负数的话，那么就在该值反码的基础上+1

直接看负数 -1 = [10000000000000000000000000000001]原码 = [11111111111111111111111111111110]反码 = [11111111111111111111111111111111]补码

这也就是上面程序中为我们输出的样子

这时候肯定有人会说了，上面取反什么得到底是怎么计算的呢，别急马上安排

位运算

在Java中，二进制间的计算可以采用以下7种方式来计算，下面我们一一来介绍

按位与：&

通过两者按位与之后，再通过左移 << 1位，即可得到两者计算下的进位信息

只有当参与计算的上下两位都为1的时候才为1，否则就为0

10 & 8 = 8  ​   00000000000000000000000000001010    & 00000000000000000000000000001000      --------------------------------      00000000000000000000000000001000

这里有一个计算 余数% 的小技巧：

当我们要计算2的N次幂的时候，采用 按位与操作 来提高效率【需要&2的N次幂二进制位全是1的那个数】

10 % 8 = 2;  10 & 7 = 2;  ​      00000000000000000000000000001010    & 00000000000000000000000000000111      --------------------------------      00000000000000000000000000000010

按位或：|

当参与计算的上下两位只要有一位上是1，那么结果就为1

1512 | 856 = 2040  ​    00000000000000000000010111101000   | 00000000000000000000001101011000    --------------------------------    00000000000000000000011111111000

异或【无进位相加】：^

正常情况下，1和1相遇需要向前一位进1，但是在异或的时候会忽略掉进位信息，只保留了最终结果

只有当参与计算的上下两位都为1的时候取0，否则就为1。

异或操作也可以这样说：

两个相同的数进行异或操作，那么它的结果必然是0

1512 ^ 856 = 1712  ​    00000000000000000000010111101000   ^ 00000000000000000000001101011000    --------------------------------    00000000000000000000011010110000

非：~

将二进制上的数全部取反

1512 = 00000000000000000000010111101000  ~1512 = 11111111111111111111101000010111

【小技巧】 当向要计算某个值的负数的时候，就可以通过取反+1的是形式来计算

左移：<<

整体向左移动指定位数，空下的位数用0填充

1      = 00000000000000000000000000000001   1 << 2 = 00000000000000000000000000000100 = 8

【小技巧】 向高位移动，也就是在该数的基础上整体多了A个2(n-1)次方，所以 如果我们想要快速计算某个数的2N次方，那么我们就可以通过 M << A 来计算 1 << 1 = 2 1 << 2 = 4 1 << 4 = 16 1 << 6 = 64 4 << 4 = 64

右移：>>

整体向右移动指定位数，除符号位外，空下的位数

正数用0补齐 负数用1补齐

8      = 00000000000000000000000000001000   8 >> 1 = 00000000000000000000000000000100         -8      = 11111111111111111111111111111000   -8 >> 1 = 11111111111111111111111111111100

这里和左移正好相反，就不再多说了

无符号右移：>>>

不管是正还是负，都整体向右移动指定位数，空下的位数用0补齐

8       = 00000000000000000000000000001000   8 >>> 1 = 00000000000000000000000000000100         -8       = 11111111111111111111111111111000   -8 >>> 1 = 01111111111111111111111111111100

实战：位图

这里我有一个需求：判断num这个数是否在某个集合中？

那么按照常规操作，我们可以会将这些数添加到Java的集合中，比如Set，然后再添加之前判断当前集合中是否存在，存在就返回true。

但是我们可以思考一个问题：假设num是int类型的

int类型占4B，如果数据有1KW的话，那么占用的内存空间是4B*1KW

如果我们可以通过通过二进制位上的0和1来表示元素是否存在，那么是不是说内存空间相对比上面的方式整整会节省32倍

一般，我们将二进制位组成的集合称之为位图【Bitmap】 ，使用它的好处就是压缩了内存空间

Redis中也存在Bitmap类型，和这个是同一个原理

那么我们就开始考虑一下如何实现吧

public class Bitmap {      int[] bits;      public Bitmap(int max) {          /**           * 这里为什么要加32？           * 为了防止max<32的情况，如果直接 max /32 的话只要小于32的都是0，但是其实这里也是要占1个数据的           */          bits = new int[(max + 32) >> 5];     }  ​      public void add(int num) {          /**           * 左边           * 将 num / 32 就可以得到num在数组中的下标位置           * 右边   * 通过左移1的二进制和或运算就可以将 数组中对应下标下对应二进制位设置为1           */          bits[num >> 5] |= 1 << (num & 31);     }  ​      public void delete(int num) {          /**           * 左边           * 将 num / 32 就可以得到num在数组中的下标位置           * 右边   * 本质上是要将对应下标下的对应位上设置为0           */          bits[num >> 5] &= ~(1 << (num & 31));     }  ​      public boolean contain(int num) {          /**           * 左边           * 将 num / 32 就可以得到num在数组中的下标位置           * 右边   * 对应位上的操作           */          return (bits[num >> 5] & (1 << (num & 31))) != 0;     }  }

难点1： 为什么 num >> 5 = num / 32?

我们在上面说过，右移N位也就是除以2N次方，那么右移5位也就是除以32喽。

难点2：为什么num & 31 = num % 32?

就是我们在通过num%32得到的结果绝对不会超过31，那么31二进制的长度为5位，那么我们通过按位与来计算余数的时候，只要保留num从左到右的5位，其他的位就全部丢弃

而31的二进制表示正好为00000000000000000000000000011111，那么当num & 31的时候，就只会留下最后的5位，其他位都是0

难点3：如何将指定位标记为1或者0？

先来看标记为1：

在难点2中得到的余数对应着num在数组中的下标位数。举个例子：余数=10，数组下标=2： 1的二进制表示为00000000000000000000000000000001，那么将它左移10位就得到了这个结果：00000000000000000000010000000000 下标2的二进制表示为00000000000000000000000000000010，和上面的结果或一下得到如下结果：00000000000000000000010000000010

此时就将对应位置标记成了1

标记为0和标记为1正好相反：

第一步都不变 第二步前半部分不变，后面要将左移的结果取反：11111111111111111111101111111111 此时和下标2的二进制按位与一下，00000000000000000000000000000010

这不就变过来了么

难点4：如何判断指定位是否为1？

下标的二进制和1左移的结果也有了，按照按位与的逻辑，只要上下都为1才能得到1的结果，那么我们就判断：

只要与下来的结果不是0，就说明那一位上标记的是1，num在该集合中是存在的

这里也介绍明白了最开始的二进制表示形式的程序

最后

其实看一看二进制的相关东西，感觉还是非常爽的。

在位图操作中，我们完全是根据位运算的特性来完成的。

我们在使用位运算的时候，虽然能够提高效率，但是在开发过程中比较难调试，出现了问题不好解决。所以在用的时候要比较细心了。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。