three ways of coding

三种编码方式：原码、反码、补码

学过大学计算机基础的人可能对原码、反码、补码有所了解，但是对于三种编码的意义一脸懵逼或是一知半解，本文希望能透彻的讲清楚三者的意义及联系。清楚地理解原码、反码、补码的概念对于编写嵌入式开发的程序有着巨大的帮助。

原码

原码由符号位、真值组成，下面给出一些例子：

二进制原码	对应十进制数
10011001	-25
00111010	57
01010110	86

原码是很直观的一个概念，就是第一位保存符号，第二位保存真值。

反码

既然有了原码，又为什么需要反码呢？这要从加减法运算讲起，如果使用原码，我们在运算时需要分两部分计算，即符号位的运算和真值的运算 ，下面用例子来说明。

算式	说明
2+3=00000010+00000011=00000101=5	正数相加，符号位一样运算后还是0，真值位直接相加
2+（-1）=00000010+10000001=00000001	正数和负数相加，符号位不一样，运算后取决于真值大的数的符号，真值位用大值减小值
-2+（-1）	负数相加，符号位相同运算后为1，真值位直接相加
2-3	符号位不同，运算后取决于真值大的数的符号，真值位用大值减小值
-3-（-2）	转换成2-3

可以看到，运算时先去括号进行符号的运算，可以归结为两种情况

1. 两个数的符号相同，如2+3，-2-3，此时符号位不变，真值位相加
2. 两个数的符号位不同，如-3+2,3-4，-4+2，此时一律当成减法来做，符号取决于真值大的数，运算结果的数组为大值减小值。

但是这样的运算法则对计算机来说是很复杂的，对于计算机如果能直接相加而不考虑符号位是最好不过的，但是我们发现2+（-1）=00000010+10000001=10000011=-3，说明原码直接相加的结果是不正确的。为了解决这一问题，反码被创造了出来。反码是在原码的基础上，对于正数保持不变；对于负数保持符号位不变，真值位取反得到的。下面给出例子：

二进制原码	二进制反码	对应十进制数
10011001	11100110	-25
00111010	00111010	57
01010110	01010110	86

现在我们再来考察一下反码的运算

算式	说明
$2+3=(00000010)_反+(00000011)_反=（00000101）_{反}=5$	正数相加，无误
2+-3=$(00000010)_反+(11111100)_反=(11111110)_反=-1$	正负数相加，负数的真值大，无误
3+-1=$(00000011)_反+(11111110)_反=(00000001)_反=1$	正负数相加，正数的真值大，出现错误
3+-2=$(00000011)_反+(11111101)_反=(00000000)_反=0$	正负数相加，正数的真值大，出现错误
-2+-3=$(11111101)_反+(11111100)_反=(11111001)_反=-6$	负数相加，出现错误
1+-1=$(00000001)_反+(11111110)_反=(11111111)_反=+0$	正负数相加且真值相等，结果为+0
+0+(+0)=$(00000000)_反+(00000000)_反=(00000000)_反=+0$ -0+(-0)=$(11111111)_反+(11111111)_反=(11111110)_反=-1$ 0+(-0)=$(00000000)_反+(11111111)_反=(11111111)_反=-0$	由于符号位的存在，导致有+0和-0之分，因此0+0有三种情况，也会产生三种结果
0+(-1)=$(00000000)_反+(11111110)_反=(11111110)_反=-1$ -0+(-1)=$(11111111)_反+(11111110)_反=(11111101)_反=-$2	同样由于$\pm0$的存在导致了不同的运算结果

综上，我们总结出规律(减法一律视为加法，硬件中没有减法器只有加法器)：

1. 正数的反码运算是正确的
2. 正数与负数相加时，当负数的真值大于等于正数时，结果正确
3. 对于正数与负数相加时，当负数的真值小于正数、负数相加的情况，结果错误但都与正确结果相差一
4. 存在+0和-0的问题

分析

• 反码的意义

  根据取反码的定义，我们可以知道对于正数无变化，对于负数相当于取真值相对于127的补，即负数反码的真值和本身的真值之和等于127。

• 正数与负数反码相加的情况

  设正数a的真值为$x_{a}$，负数b的真值为$x_{b}$，记a的反码为$\tilde a$;记b的反码为$\tilde b$，则取反码后：

  $\tilde a$的真值为$x_{a},\tilde b$的真值为$127-x_{b}$

  那么$\tilde a + \tilde b$的真值为$127+x_{a}-x_{b}$,这里会产生一个进位问题：

  • 当$x_{b}127产生进位，符号位因为进位置零。相应的实际上正数大于负数,符号 位 正确。

    结果的真值为$x_{a}-x_{b}-1$与正确结果相差1，可知错误的产生是由于进位

  • 当$x_{b}>x_{a}$时，$127+x_{a}-x_{b}>127$不进位,符号位任为1，相应的实际上正数小于负数,符号位正确。

    结果真值为$x_{b}-x_{a}$,结果正确，到此与上表相符。

• 对于负数相加的情况，结果的真值为$254-x_{a}-x_{b}$，因为不能溢出，所以$x_{a}+x_{b}<=127$

  • 当$x_{a}+x_{b}<127$ 时，会发生一个进位，符号位因此置1，符号正确，结果真值为$x_{a}+x_{b}-1$,与上表相符。
  • 当$x_{a}+x_{b}=127$时，不进位，符号位置0，符号错误，结果真值为127，结果错误

总的来看采用反码来运算有以下问题：

1. $\pm$ 0的问题
2. 进位导致的偏差
3. 边界运算的跳变

补码

为了解决反码存在的问题，补码应运而生。在将补码之前，我们来看看如何改进反码。

由上面的分析，我们发现进位的产生导致运算结果与正确的结果相差1，那么我们可以进行修正，由于正数之间的运算没有问题，那么我们不能修正正数，因为这样会引起正数运算的错误，于是我们应该对负数进行修正。

根据式$x_{a}-x_{b}-1$（正负数相加的情况），保持$x_{a}$不变，则只能将-$x_{b}$修正为1-$x_{b}$，往上追溯即把$\tilde b $的真值修正为$128-x_{b}$，即负数b在取反的基础上，再加一(逆回去的时候也是如此)，经过验证，我们发现负数相加时的问题也解决了。

巧合的是，此时边界问题也得到了解决，简单的来看，我们可以这么想：负数相加，两个数都多加了1，逆回去要减去1，总的来看修正了1；正负数相加，正数大于负数时，负数多加了1，运算结果由于是正的，逆回去的时候不再减1，总的来看修正了1；正负数相加，负数大于正数，负数多加了1，运算结果由于是负的，逆回去的时候减去1，总的来看修正零。这样我们就把上面的错误都修正了。

再来看一下$\pm0$的问题，我们发现+0取反加1后为00000000，-0取反加1后也为00000000，因此$\pm0$在某种程度上得到了统一。

在这里我们引出补码，补码的一种计算方式就是取反加一（对于负数，正数补码是本身），但是切记补码不是通过反码定义的，这只是一种巧合而已。在反码中，我们还做了一个规定是-128=10000000，这是因为用补码表示数的时候0只有一种补码，这导致补码少了一个，即10000000没有出现，因此扩充定义。但是-128没有反码，它不在反码表示范围之内。

补码的真正含义

不管是补码还是反码，它们都是为了解决带符号运算的问题的。由于数值类型的限制，确定的类型的长度是固定的，因此我们可以通过舍弃进位的方式将负数转为正数。

以8位的数为例：

3+（-2）与3+（256-2）=00000011+（100000000-00000010）=00000011+11111110=00000001

两者的结果是一样的，因为后者产生了一个进位（一个进位代表了256的产生）舍弃后结果也为1。这里不得不拿钟来说事，假设现在钟显示3点，但是走快了一个小时，我们要把它调到2点，方式有两种——我们既可以往后拨1个小时也可以往前拨23个小时，这是因为钟表上只能记录0-23这24个数，3+23=26并不在其中，只能丢弃一个24变为2。因此我们不能分清2与26的区别，也就是说（假设x+y=res,y为负数）我们完全有理由可以认为$x+y’=res+256$，为保证等式的成立，必然有等价关系$y+256=y’$（解x，根据对应相等得出）

按这种方式，我们实际上是对负数做了一个映射，关系为当x为正数时x+256无变化；当x为负数时$x_{补}=256-|x|$,这样x+y和256-|x|+y在丢弃进位后是一样的。这样，我们构建了这样一个世界：一切减法变加法，一切负数变正数，想求原值逆映射。

下面我们再解释一下为什么负数补码等于反码加一。假设负数x的真值为a,则由于取反保留了符号位，相当于加了10000000即128，真值部分取反，得到的结果的真值为127-a，那么取反得到的数相当于128+127-a=255-a，再加上1等于256-a即补码的定义。

最后给出补码的数学验证，这里我们会用到同余的概念。如果两个数除以同一个数得到的余数相等，则这两个数关于除数同余，例如11%4==35%4，则11与35关于4同余，记为$11\equiv35(mod \ \ 4)$

由于(x为负数)$x=-|x|\equiv 256-|x|(mod \ \ 256)$,并且$y\equiv y(mod \ \ 256)$,则根据同余的线性运算法则有：

$$\begin{align} y-|x|=x+y\\ x+y\equiv x+y+256(mod \ \ 256)\\ x+y+256=y-|x|+256=x_{补}+y_{补}\\ \therefore x+y \equiv x_{补}+y_{补}(mod \ \ 256) \end{align}$$

在限定了数的范围之后，同余数x+y和x+y+256是一样的，拿钟来说就是相差一圈，但是就结果而言我们无法区分这两种情况，这是一种等效的思想。