数学篇：带你了解二进制

计算机的起源是数学中的二进制计数法。可以说，没有二进制，就没有如今的计算机系统。那什么是二进制呢？为什么计算机要使用二进制，而不是我们日常生活中的十进制呢？如何在代码中操作二进制呢？接下来带你详细了解二进制，嘻嘻???? ，开始吧～

什么是二进制计数法？

以二进制数字 110101 为例。这里 110101 究竟代表了十进制中的数字几呢？

十进制计数是使用 10 作为基数，那么二进制就是使用 2 作为基数，类比过来，二进制的数位就是 2^n 的形式。如果需要将这个数字转化为人们易于理解的十进制，我们就可以这样来计算：

按照这个思路，我们还可以推导出八进制（以 8 为基数）、十六进制（以 16 为基数）等等计数法。

至此，我们应该已经理解了什么是二进制。但是仅有数学的理论知识是不够的，结合相关的代码实践，相信你会有更深刻的印象。

基于此，我们来看看二进制和十进制数在 JS 中是如何互相转换的，并验证一下我们之前的推算。我这里使用的是 JS 来实现的，其他主流的编程语言实现方式都是类似的。

let num = 53;
let num2 = num.toString(2) // "110101"
>>> "110101"

num = parseInt( num2, 2) // 53
>>> 53

可以看到：十进制数字 53 的二进制是 110101，二进制数字 110101 的十进制是 53。，关于十进制和二进制的概念以及进制之间的相互转换，应该都很清楚了。既然有十进制，又有二进制，你可能就要问了，为啥计算机使用的是二进制而不是十进制呢？

计算机为什么使用二进制？

计算机使用二进制和现代计算机系统的硬件实现有关。组成计算机系统的逻辑电路通常只有两个状态，即开关的接通与断开。

断开的状态我们用“0”来表示，接通的状态用“1”来表示。由于每位数据只有断开与接通两种状态，所以即便系统受到一定程度的干扰时，它仍然能够可靠地分辨出数字是“0”还是“1”。因此，在具体的系统实现中，二进制的数据表达具有抗干扰能力强、可靠性高的优点。

相比之下，如果用十进制设计具有 10 种状态的电路，情况就会非常复杂，判断状态的时候出错的几率就会大大提高。

另外，二进制也非常适合逻辑运算。逻辑运算中的“真”和“假”，正好与二进制的“0”和“1”两个数字相对应。逻辑运算中的加法（“或”运算）、乘法（“与”运算）以及否定（“非”运算）都可以通过“0”和“1”的加法、乘法和减法来实现。

二进制数的表示

为了实现不同的目的，其实都是为了简化问题，二进制数在计算机中有不同的表示方法，如原码、反码、补码和移码等。为了简化运算，下面二进制数都是用一个字节——8个二进制位来简化说明

真值

我们用二进制表示自然数包括正数，负数和0。下面是1和-1的二进制表示，我们称为真值

+ 00000001 # +1
- 00000001 # -1

8位二进制数能表示的真值范围是[-2^8, +2^8]。

原码

由于计算机只能存储0和1，不能存储正负，所以用8个二进制位的最高位来表示符号，0表示正，1表示负，用后七位来表示真值的绝对值，这种表示方法称为原码表示法，简称原码，上面的1和-1的原码如下：

0 0000001 # +1
1 0000001 # -1

由于10000000的意思是-0，这个没有意义，所有这个数字被用来表示-128，所有负数就比整数多一个。

由于最高位被用来表示符号了，现在能表示的范围是[-2^7, +2^7-1]，即[-128, +127]

反码

反码是另一种表示数字的方法，其规则是正数的反码和其原码一样，负数的反码将其原码的符号位不变，其余各位按位取反

0 0000001 # +1
1 1111110 # -1

反码的表示范围是[-2^7, +2^7-1]，即[-128, +127]

补码

补码是另外一种表示方法，主要是为了简化运算，将减法变为加法而发明的数字表示法，其规则是正数的补码和原码一样，负数的补码是其反码末尾加1

0 0000001 # +1
1 1111111 # -1

快速计算负数补码的规则就是，由其原码低位向高位找到第一个1，1和其低位不变，1前面的高位按位取反即可。

8位补码表示的范围是[-2^7, +2^7-1]，即[-128, +127]

32个比特位表示的整数

js中还有另一种类型的数据，那就是用32个比特位表示的整数，只要对js中的任何数字做位运算操作系统内部都会将其转换成整形，例如

2.1 | 0 # 或运算
>>> 2

js中的这种整形是区分正负数的，我们根据上面的知识推断js中的整数的表示范围是[-2^31, +2^31-1]，即[-2147483648, +2147483647]，在控制台输出下面的代码来验证我们的推断

-2147483648 | 0
>>> -2147483648

-2147483649 | 0
>>> 2147483647

2147483647 | 0
>>> 2147483647

2147483648 | 0
>>> -2147483648

从上面的结果可以看出，大于和小于最低和最高的值再去进行转换时都将改变正负号

二进制的位操作

了解了现代计算机是基于二进制的，我们就来看看，计算机语言中针对二进制的位操作。这里的位操作，也叫作位运算，就是直接对内存中的二进制位进行操作。常见的二进制位操作包括向左移位和向右移位的移位操作，以及“或”“与”“异或”的逻辑操作。

向左移位

二进制 110101 向左移一位，就是在末尾添加一位 0，因此 110101 就变成了 1101010。请注意，这里讨论的是数字没有溢出的情况。(数字溢出:就是二进制数的位数超过了系统所指定的位数。目前主流的系统都支持至少 32 位的整型数字，而 1101010 远未超过 32 位，所以不会溢出。如果进行左移操作的二进制已经超出了 32 位，左移后数字就会溢出，需要将溢出的位数去除。)

在这个例子中，如果将 1101010 换算为十进制，就是 106，你有没有发现，106 正好是 53 的 2 倍。所以，我们可以得出一个结论：二进制左移一位，其实就是将数字翻倍。

向右移位

二进制 110101 向右移一位，就是去除末尾的那一位，因此 110101 就变成了 11010（最前面的 0 可以省略）。我们将 11010 换算为十进制，就是 26，正好是 53 除以 2 的整数商。所以二进制右移一位，就是将数字除以 2 并求整数商的操作。

下面我们来看看，用代码如何进行移位操作。

可以看到：数字 53 向左移 1 位是 106；数字 53 向右移 1 位是 26。

其中，移位 1 次相当于乘以或除以 2，而移位 3 次就相当于乘以或除以 8（即 2 的 3 次方）。

左移位是 <<，那右移位是 >>，其实 右移 >>> 也是可以的标示逻辑右移。简单来说，之所以有这两种表达方式，根本原因是 JS 的二进制数值中最高一位是符号位。

由于计算机只能存储0和1，不能存储正负，所以用二进制位的最高位来表示符号，0表示正，1表示负，用后七位来表示真值的绝对值，这种表示方法称为原码表示法，简称原码

详细解释一下

我们以 数字 53 的二进制为 110101，从右往左数的第 32 位是 0，表示该数是正数，只是通常我们都将其省略。

如果数字是 -53 呢？那么第 32 位就不是 0，而是 1。请注意我这里列出的是补码。

那么这个时候向右移位，就会产生一个问题：对于符号位（特别是符号位为 1 的时候），我们是否也需要将其右移呢？因此，JS及JAVA定义了两种右移，逻辑右移和算术右移。逻辑右移(>>>) 1 位，左边补 0 即可。

算术右移(>>)时保持符号位不变，除符号位之外的右移一位并补符号位 1。补的 1 仍然在符号位之后。

逻辑右移在 JS、Java 、Python 等语言中使用 >>> 表示，而算术右移使用 >> 表示。 我们来看下 53 及 -53 执行 算数右移 和 逻辑右移的执行结果

在 C 或 C++ 语言中，逻辑右移和算数右移共享同一个运算符 >>。那么，编译器是如何决定使用逻辑右移还是算数右移呢？答案是，取决于运算数的类型。如果运算数类型是 unsigned，则采用逻辑右移；而是 signed，则采用算数右移。如果你针对 unsigned 类型的数据使用算数右移，或者针对 signed 类型的数据使用逻辑右移，那么你首先需要进行类型的转换。

由于左移位无需考虑高位补 1 还是补 0（符号位可能为 1 或 0），所以不需要区分逻辑左移和算术左移。

位的“或”

我们刚才说了，二进制的“1”和“0”分别对应逻辑中的“真”和“假”，因此可以针对位进行逻辑操作。

逻辑“或”的意思是，参与操作的位中只要有一个位是 1，那么最终结果就是 1，也就是“真”。如果我们将二进制 110101 和 100011 的每一位对齐，进行按位的“或”操作，就会得到 110111。

位的“与”

同理，我们也可以针对位进行逻辑“与”的操作。“与”的意思是，参与操作的位中必须全都是 1，那么最终结果才是 1（真），否则就为 0（假）。如果我们将二进制 110101 和 100011 的每一位对齐，进行按位的“与”操作，就会得到 100001。

位的“异或”

逻辑“异或”和“或”有所不同，它具有排异性，也就是说如果参与操作的位相同，那么最终结果就为 0（假），否则为 1（真）。所以，如果要得到 1，参与操作的两个位必须不同，这就是此处“异”的含义。我们将二进制 110101 和 100011 的每一位对齐，进行按位的“异或”操作，可以得到结果是 10110。

“异或”操作的本质其实就是，所有数值和自身进行按位的“异或”操作之后都为 0。而且要通过“异或”操作得到 0，也必须通过两个相同的数值进行按位“异或”。这表明了两个数值按位“异或”结果为 0，是这两个数值相等的必要充分条件，可以作为判断两个变量是否相等的条件。

js中的位运算

上面讲解了 位运算 的相关概念，接下来我们看下在JS中的位运算。 js中的位运算符有下面这些，对数字进行这些操作时，系统内部都会讲64的浮点数转换成32位的整形

& 与
| 或
~ 非
^ 异或
<< 左移
>> 算数右移(有符号右移)
>>> 逻辑右移(无符号右移)

下面举例子来说明每个运算符的作用，开始之前先来介绍几个会用到的知识点

原生二进制字面量

es6中引入了原生二进制字面量，二进制数的语法是0b开头，我们将会用到这个新功能，目前chrome最新版已经支持。

0b111 // 7
0b001 // 1

Number.prototype.toString

Number.prototype.toString方法可以讲数字转化为字符串，有一个可选的参数，用来决定将数字显示为指定的进制，下面可以查看3的二进制表示

3..toString(2)
>> 11

<< 左移

左移的规则就是每一位都向左移动一位，末尾补0，其效果相当于×2，其实计算机就是用移位操作来计算乘法的

010
---
0100

010左移一位就会变为100，下面在js中验证

(0b010<<1).toString(2)
>>> "100"

>> 算数右移(有符号右移)

算数右移也称为有符号右移，也就是移位的时候高位补的是其符号位，正数则补0，负数则补1

(0b111>>1).toString(2)
>>> "11"

(-0b111>>1).toString(2)
>>> "-100"

负数的结果好像不太对劲，我们来看看是怎么回事

-111 // 真值
1 0000111 // 原码
1 1111001 // 补码
1 1111100 // 算数右移
1 0000100 // 移位后的原码
-100 // 移位后的真值

>>> 逻辑右移(无符号右移)

逻辑右移又称为无符号右移，也就是右移的时候高位始终补0，对于正数和负数右移没有区别

(0b111>>>1).toString(2)
>>> "11"

对于负数则就不同了,右移后会变为正数

(-0b111>>>1).toString(2)
>>> "1111111111111111111111111111100"

& 与

&按位与会将操作数和被操作数的相同为进行与运算，如果都为1则为1，如果有一个为0则为0

101
011
---
001

101和011与完的结果就是001，下面在js中进行验证

(0b101 & 0b011).toString(2)
>>> "1"

| 或

|按位或是相同的位置上只要有一个为1就是1，两个都为0则为0

101
001
---
101

101和001或完的结果是101，下面在js中进行验证

(0b101 | 0b001).toString(2)
>>> "101"

~ 非

~操作符会将操作数的每一位取反，如果是1则变为0，如果是0则边为1

101
---
010

计算规则

~x = -(x+1);

101按位非的结果是010，下面在js中验证

(~0b101).toString(2)
>>> "-110"

发现 怎么结果不对呢？我们回顾下如下规则：

• 计算机中的数字是以 补码 的形式表示的
• 正数的原码、反码、补码都一样，就是它本身
• 负数的反码符号位不变，其余取反；补码为反码加1
• +0的补码和-0一样（其实不一样，-0的进1被丢弃了）
• 取反的意思每位0变1、1变0 所以

0 0000101 // 原码
0 0000101 // 反
0 0000101 // 补
1 1111010 // 取反
1 0000110 // 原码

原码先求出反码，反码取反，之后再求出其原码，也就是最后的结果显示-110

我们再来看下 1 和 -1 求非 的过程：

对于操作数1：这个取反的结果不大好看，但是我们知道，~x = -(x+1)，我们计算一下啊：~1 = -(1+1) = -2，那我们看看-2的补码吧，如果补码就是11111111,11111111,11111111,11111110

可以看到，-2的补码果然是11111111,11111111,11111111,11111110，这就是-2，这就是它在计算机中的表现形式。

其实上面的与和或也都是会操作符号位的，不信你试试下面这两个，可以看到符号位都参与了运算

(0b1&-0b1)
>>> 1

(0b1|-0b1)
>>> -1

^ 异或

异或顾名思义看看两个位是否为异——不同，两个位不同则为1，两个位相同则为0

101
001
---
100

101和001异或的结果是100，js中验证

(0b101^0b001).toString(2)
>>> "100"

小结一下

二进制贯穿在很多常用的概念和思想中，例如逻辑判断、二分法、二叉树等等。逻辑判断中的真假值就是用二进制的 1 和 0 来表示的；二分法和二叉树都是把要处理的问题一分为二，正好也可以通过二进制的 1 和 0 来表示。因此，理解了二进制，你就能更加容易地理解很多计算机的数据结构和算法，也为我们后面的学习打下基础。