编码与原码、补码、反码
# 30.编码与原码、补码、反码
介绍下计算机常用的编码方式
# 什么是信息
在讲什么是编码之前，先讲一下什么是信息。不同的学科对信息这个单词的解读都不一样。我们这里可以简单的理解为信息就是知识的传递，它描述了一种状态或者一个事实。
那么我们如何传递信息呢？这就需要用到编码。
比如我有这样一个信息：今天是 2020 年 1 月 1 号。我可以用文字的形式将其表示出来，也可以用语音的形式向其表示出来，还可以用手语或者用盲文将其表示出来。在这里文字是一种编码的形式，语音也是一种编码方式。手语和盲文也是一种编码的形式。数字的发明，应该是人类最早的编码文明。
我们这里下一个定义。码制就是表示事物的规则。这里的码制就是指文字，语音，手语和盲文。
将阿拉伯数字表示成其他进制中的数，也是一种编码方式。但我们要注意，即使是在其他进制中，数字也是可以做加减乘除四则运算的，也是可以进位的。
# 原码
我们如果要表示一个数的二进制数方式，我们可以直接写出它的二进制数，但如何表示一个负的二进制数呢？在我们日常使用十进制数进行运算时，我们是用一个负号“-”，放到数字前面表示这是一个负数。
当然我们手工计算二进制时，这样做也是可以的。
而在计算机中，我们并没有表示负号的机制。计算机只能处理 0 或者 1。
那我们可不可以在二进制数之前加一位数，例如 0 表示正数，1 表示负数？当然是可以的。我们称这样的编码方式为原码。
例如 +5 可以这样表示 0 0101， -5 可以这样表示 1 0101
但如果我们直接用原码去做二进制计算，是不可以的。例如上述的两个数相加，结果应该是 0，但如果我们这样表示二进制数，和我们想要的结果不符合：
0 0101
1 0101
1 1010
2
3
1 1010 表示的是-9！为什么呢？因为我们这里用 0 表示负数，1 表示正数，这其实是一种编码方式，不是一种数学中进位的方式，我们这里将码制跟数制混合起来了，这是一种混合的编码方式。
最高位的 1 代表的是这个数是正还是负，而不是表示数字。也就是这样混合编码的话，四则运算就失效了。
所以如果我们要用原码计算，必须先比较出两数的绝对值，然后相减，得到差值。这个方法很麻烦，用电路实现的话还需要用到比较电路和减法电路。
我们知道，二进制的加法是很简单的，无非就是：
- 0 + 0 = 0
- 0 + 1 = 1
- 1 + 1 = 10
即使是多位二进制数，进位也只需要一位一位往前进就行。
而如果一旦涉及到减法，就要考虑借位了。而用电路实现借位，是非常麻烦的。我们先来做一道十进制的减法题：
2 5 3
- 1 7 6
= 7 7
2
3
要做这道题，从最右边一列开始。首先，6 比 3 大，所以需要从 5 借 1，这样就变成了 13 减 6，结果是 7。
由于从 5 借了 1，5 就变成了 4，4 比 7 小，所以继续从 2 借 1，14 减 7 等于 7。
2 被借 1 后成为 1，1 减 1 为 0，所以最后结果是 77。
幸运的是，早于十六世纪，法国数学家布莱士·帕斯卡（Blaise Pascal 1623-1662）早已想到办法，通过某种方式，可以将减法变为加法，这样，只需要加法电路，我们就可以完成加减法了！该方法就是补码，计算机中沿用至今。
# 补码
模、补数：在日常生活当中，可以看到很多这样的事情：
- 把某物体左转 90 度，和右转 270 度，在不考虑圈数的条件下，最终的效果是相同的；
- 把分针倒拨 20 分钟，和正拨 40 分钟，在不考虑时针的条件下，效果也是相同的；
- 把数字 87，减去 25，和加上 75，在不考虑百位数的条件下，效果也是相同的；
- ……
上述几组数字，有这样的关系：
- 90 + 270 = 360
- 20 + 40 = 60
- 25 + 75 = 100
式中的 360、60 和 100，就是“模”。式中的 90 和 270、20 和 40，以及 25 和 75，就是一对对“互补”的数字。
知道了“模”，求某个数字的“补数”，就是轻而易举的了：如果模为 365，数字 120 的补数为：365 - 120 = 245。
用补数代替原数，可把减法转变为加法。出现的进位就是模，此时的进位，就应该忽略不计。
有了补码，我们怎么计算呢？举例，有个小孩，只能认识 100 个数。超过 100，就从 0 开始数。他很小，只会加法，还不会做减法。可以这样教他：减一，就用加上 99 代替。因为：
- 28 －1 ＝ 27， 减去 1，等于加上 1 的补数， [1] 补 = 模（100） - 1 = 99
- 28 + 99 ＝ (1)27
同样，减二，可以用加上 98 代替；
- －3，可以用 ＋97 代替；
- －4，可以用 ＋96 代替；
- …… 以此类推
在 100 个数字的范围内：
1、99，是一对互补的数字。
2、98，也是。
用互补的数，代替原数，即可把减法，转换成加法。注意，要忽略进位。
有补码的好处：用了补码，就不用借位了。这句话是重点，重点，重点。例如：
28 －1 = 28 - （100 - 99） = 28 + 99 - 100，这样，28 和 99 相加，是不用借位的；
但我们求 -1 的补码，100 - 99，还是要借位，怎么办呢？我们可以转换成这样：
28 - 1 = 28 -（99 -99 +1） = 28 +99 -99 -1 = 28 + 99 - （99 + 1）= 28 + 99 -100。
我们再举一个例子，求 - 66 的补码：
[66]补 = 模 - 66 = 100 - 66 = 99 + 1 -66 = 99 -66 +1
其中，99 - 66 也是不用借位的。
以上是求补码的原理，也是二进制求补码的原理。
现在，我们回到二进制。在八位二进制数字的范围内，共有 256 个数字。0000 0000～1111 1111，即 0～255。
- 1、255，是一对互补的数字。
- 2、254，也是。
- ……以此类推；
那么，－1，就可以用 +255 代替。－2，也就可以用 +254 代替。即：
[－1] 补 ＝255。
[－2] 补 ＝254。
计算时，加上正数，是不需要求取补数的；只有进行减法（或者加上负数），才需要对减数求补数。
由此，我们引申出补码的定义：
- 正数不变；
- 负数即用模减去绝对值。
那么，已知一个数 N ，其 8 位字长的补码定义为：
- [N]补 ＝ X ……………0 <= N <= +127，正数和 0 的补码，就是该数字本身
- [N]补 ＝ 28－|N|…… -28 <= X < 0，负数的补码，就是用模，减去该数字的绝对值
计算机的书上，一般，都有这个定义式。
我们引申下补码的通用定义：对于有效数字（不包含符号位）为 n 位的二进制数 N，它的补码 (N) comp 表示如下：
- (N) comp＝ N （当 N 为正数）
- (N) comp＝ 2n－N…… （当 N 为负数）
但是，求补码的过程中，还是有涉及到借位，怎么办呢？我们可以这样：例如有效位数为 8，求 (-26) 10的二进制补码，我们可以先求出其二进制原码为： 0001 1010
然后，就是用 28 - 0001 1010：
1 0000 0000
- 0001 1010
2
为了不借位，我们可以将 28 变成 2 -1 + 1。 因为 28 = 2 -1 + 1
其中，2 -1 = (1111 1111)2
那么，28 - 0001 1010 可以变成这样子：
1111 1111
+ 1
- 0001 1010
2
3
我们调换下顺序：
1111 1111
- 0001 1010
+ 1
2
3
因为在一个二进制数中，只有 0 和 1,1 是最大的， 1 减去 1, 1 减去 0，都不用借位。而且，我们观察到，1-1=0， 1-0 = 1
从结果来看，我们把被减数的每一个结果取反（1取反得0,0取反得1），就能得到结果，我们还要必要做减法吗？
(1111 1111) - (0001 1010) 的结果，和我们直接取反(0001 1010) 的结果，是一样的。然后我们再加上 1，不就得到补码了吗？
练习：-10 的原码：1000 1010 -10 的补码：1111 0110 符号位是 1
# 反码
由此我们引申出的定义：二进制数 N 的反码 (N)inv 的定义：
- (N)inv = N 当 N 为正数
- (N) inv= 2n - 1 - N 当 N 为负数
2n - 1 是 n 位全为 1 的二进制数，所以求负数的补码的时候，只要将负数的每一位 1 改为 0, 0 改为 1，也就是取反，就可以得到反码了。后续我们会看到，在电路上，实现取反一个二进制数是很容易的（至少比实现借位方便）。
# 小结
我们求补码的话，一般是采用取反加一的办法，希望你能理解它的原理，而不是死记硬背。
# 原码、反码、补码对照表
这里以 4 位二进制数为例 （8 位的太多了）
| 十进制数 | 二进制原码（带符号数） | 二进制反码 | 二进制补码 |
|---|---|---|---|
| +7 | 0111 | 0111 | 0111 |
| +6 | 0110 | 0110 | 0110 |
| +5 | 0101 | 0101 | 0101 |
| +4 | 0100 | 0100 | 0100 |
| +3 | 0011 | 0011 | 0011 |
| +2 | 0010 | 0010 | 0010 |
| +1 | 0001 | 0001 | 0001 |
| +0 | 0000 | 0000 | 0000 |
| -1 | 1001 | 1110 | 1111 |
| -2 | 1010 | 1101 | 1110 |
| -3 | 1011 | 1100 | 1101 |
| -4 | 1100 | 1011 | 1100 |
| -5 | 1101 | 1010 | 1011 |
| -6 | 1110 | 1001 | 1010 |
| -7 | 1111 | 1000 | 1001 |
| -8 | 1000 | 1111 | 1000 |
# 补码与十进制转换
如何通过负数的二进制补码求十进制数? 可以看成 第一位是 -127 的权重，在清华大学的课程这样说道：
大家看最高位，在以前的编码的时候，我们是不是把它当成了一个符号位？所谓符号位是不是认为它不带大小，对吗？
但是如果当你进行补码编码的时候，我们可以当它是一个带符号的，同时也是带大小的这么一个权值，一个负的权值。
例如我们求 (1001)2 的补码，表示的十进制数是多少，两种方法：
- 减一后取反。 1001 - 1 = 1000 ，取反后就是 0111 ，也就是 -7 的补码
- 我们可以理解为，第一位二进制数是带符号的， 后续的每一位二进制数都是不带符号的，那么 (1001)2 就可以理解为是 1×（-23） + 0 × 22 + 0×21 + 1×20 = - 8 + 1 = -7
数字 0 ~＋127，直接就是补码。
数字 -128 ~ -1，是用 128~255 当作补码。
# 一些术语
最后说一些英文术语：
补码：Complement，英语里又叫 two's complement（对 2 求补）
反码：Inverse code
有些教材会称反码为 1 的补码， 1's Complement
