Number System
⚠ 转载请注明出处：作者：ZobinHuang，更新日期：Feb.6 2021
本文将描述计算机内部是如何表示数据并且进行各种计算操作的。
1. 二进制基本原理
1.1 二进制
对于计算机，使用的是我们熟知的二进制表示方法：
D=(dp1⏟MSBdp2...d1d0.⏟小数点d-1d-2...d-n⏟LSB)2=p1∑i=-ndi⋅2i
1.2 二进制与十进制的相互转化
1.2.1 二进制转十进制
对于任意的数值系统来说，其转换为十进制的方法都是（尤其注意小数部分）：
D=DInteger+DFraction=(dn-1⋅rn-1+dn-2⋅rn-2+...+d1⋅r1+d0⋅r0)⏟Integer+(d-1⋅r-1+d-2⋅r-2+...+d-m⋅r-m)⏟Fraction
1.2.2 十进制转二进制
(1) 整数部分(以十进制数179为例)
2⌊89̲......1
2⌊44̲......0
2⌊22̲......0
2⌊11̲......1
2⌊5̲.......1
2⌊2̲.......0
2⌊1̲.......1
如上图所示，我们不断地将179除以2，将每一次除法得到的余数记录下来，最终二进制的结果就是从底到顶的01序列，即10110011。这种计算方法的原理是：第n次除以二时，得到的余数就是所需要的2n-1的个数（在二进制中只有0个或者1个）。具体演算如下：
2⋅89=2⋅(2⋅44+1)=4⋅44+1⋅2⏟21
4⋅44=4⋅(2⋅22+0)=8⋅22+0⋅4⏟22
8⋅22=8⋅(2⋅11+0)=16⋅11+0⋅8⏟23
16⋅11=16⋅(2⋅5+1)=32⋅5+1⋅16⏟24
32⋅5=32⋅(2⋅2+1)=64⋅2+1⋅32⏟25
64⋅2=64⋅(2⋅1+0)=128⋅1+0⋅64⏟26
128⋅1=1⋅128⏟27
因此，179=1⋅20+1⋅21+0⋅22+0⋅23+1⋅24+1⋅25+0⋅26+1⋅27=(10110011)2
(2) 小数部分(以十进制数0.17为例)
下面讲述一下整个演算的过程和原理。首先我们将0.17连续乘以2直到积大于1为止。
0.34⋅2=0.68......0
0.68⋅2=1.36......1
我们发现乘了3次之后积是1.36，因此组成0.17的最大的2的整数次幂是2-3=123=0.125。然后我们就得开始找组成(0.17-0.125)=0.045这个部分的2的整数次幂。其实我们不用独立去计算下一个要找哪个数的最大2的整数次幂，更方便的方法是我们取出积1.36的小数部分，即0.36，因为0.36是(0.17-0.125)=0.045被放大23=8倍的结果。
0.72⋅2=1.44......1
我们使用同样的连续乘2来处理0.36直到积大于1，乘了2次2之后我们得到积1.44，因此组成0.36的最大的2的整数次幂是2-2=122=0.25，除去前面被放大的23=8倍，组成0.045的的最大的2的整数次幂是0.258=2-5=125=0.03125。如上道理，我们取出0.44并继续找组成0.44以及后续数的最大2的整数次幂。根据精度要求找到在精度范围内所有2的整数次幂，就能完成小数部分的二进制转化工作。
0.88⋅2=1.76......1
0.76⋅2=1.52......1
......
综上，我们得到0.17的二进制表示方法是2-3+2-5+2-7+2-8=(0.00101011)2。
2. 二进制四则运算
二进制四则运算的运算规则和十进制相似，在脑中过一遍计算过程有助于后序讨论如何用电路实现二进制运算电路。
1.3.1 二进制加法
二进制加法规则与十进制相似，不再赘述。
1.3.2 二进制减法
二进制减法规则与十进制相似，区别就是每一次不够减借位是借2。
1.3.3 二进制乘法
二进制乘法规则与十进制相似。通常使用移位和加法的操作来实现乘法。
1.3.4 二进制除法
二进制除法规则与十进制相似，不再赘述。
3. 二进制负数的表示
3.1 我们为什么要二进制负数表示？
后面的文章将会看到，对于加法器可以很简单地用数字电路搭建出来，因此可以使用电路很简单地实现二进制数的加法操作。其它的运算都需要转化为加法操作。对于减法，最直接的办法就是想办法使用二进制数来表示负数，然后就能将 A-B 转化为 A+(-B)。因此我们先明确一点：讨论二进制负数表示的意义在于可以找到一种负数表示方法，使得加法电路可以用来做减法操作。在本节我们会介绍几种二进制表示负数的方法，其中我们重点关注补码。
3.2 模(Modulo)的概念
模指的是一个有限计数系统的计数范围。比如时钟，模是12，计数范围是0~11；四位寄存器，模是24=16，计数范围是0~15。有限计数系统的最大特点在于其有补数的性质。举个例子，假设当前时针指向11点，而准确时间是8点，调整时间可有以下两种拨法：一种是倒拨3小时，即11-3=8，另一种是顺拨9小时即11+9=12+8=8，可以看出，在以模为12的系统中，加9和减3效果是一样的，因此凡是减3运算，都可以用加9来代替。对“模”12而言，9和3互为补数（二者相加等于模）。所以我们可以得出一个结论：在有限计数系统中，减一个数等于加上它的补数，从而实现将减法运算转化为加法运算的目的。
3.3 Twos'-Complement(补码)表示法
基于上面时钟系统的讨论，可以发现，我们能将补数用于我们的二进制编码系统，从而实现将减法操作转化为加法操作，以使用我们的加法电路来实现减法。我们将这套系统称为补码系统，如上图所示。对于正数和0，我们保持和正常计数方法一样不变。对于负数，我们使它们的值等于它们绝对值所对应补数的值。例如上图所示的四位系统，-1的值为 f补数(1)=15=(1111)2 ，-3的值为 f补数(3)=13=(1101)2。你可能会有疑问，那这些补数(i.e. 前面例子中的15，13)怎么表示呢？由于n位补码系统的表示范围是 2-(n-1)~2n-1-1，如上面的例子中是-8~7，因此负数们所对应的补数根本就无法出现在计算系统中，因此就没有了这些补数该如何表示的顾虑。下面，我们考虑一个四位的计算机系统，其模是16，对计算式5-3的计算过程进行分析。
5-3
=5+(16-3) 【套用补数的概念】
=5+((10000)2-(0011)2)
=5+(1+(1111)2-(0011)2)
=5+(1+(1100)2) 【此处我们可以发现负数的补数的简单求法：该负数的反码+1】
=(0101)2+(1101)2 【-3的补码即1101】
=(10010)2 【由于是4位计算机系统，因此最高位1溢出】
=(0010)2
=2
综上，我们找到了补码这一能够让我们方便地使用加法电路完成减法操作的计数系统。负数的补码值其实有另一种简单的求法，上面的过程只是为了更好的理解补码的意义所在，这种简单的求法就是众所周知的：负数反码值加一。下面简单介绍其它两种计数方法：原码和反码。
3.4 Signed-Magnitude(原码)表示法
原码表示法采用最高一位比特作为符号位，0代表正数，1代表负数。原码的优势在于取反操作十分简单，但是其缺点在于：(1)有两种0的表示方法；(2)无法对原码进行计算操作。因此显然原码并不适用于我们的需求。
3.5 Ones'-Complement(反码)表示法
反码表示法表示负数的方法是反转每一位比特，如上第一幅图所示。在上面第二副图中，我们发现对于MSB位的carry out为0的加法计算，是可以通过直接对反码进行计算得到正确结果的，但是如果MSB位的carry out为1，则结果会出问题，必须在结尾在加上一个1，才能得到正确的结果，这种现象会导致计算电路变得十分复杂。
3.6 总结
4. 二进制小数的表示
4.1 定点数
4.1.1 定点数表示方法
定点数表示法指的是使用某些特定比特位作为整数部分，剩余特定比特位作为小数部分。以数6.75为例，若我们使用四个比特表示整数部分，另四个比特表示小数部分，则可以得到(01101100)2，我们在其中其实省略了一个小数点，即(0110.1100)2。
4.1.2 使用补码来表示有符号定点数
值得一提的是带符号的定点数，我们同样可以使用补码来表示定点数。以数-6.75为例，根据我们上面讨论的补码的定义：对于负数，我们使它们的补码值等于它们的绝对值所对应补数的值，我们考虑6.75所对应的补数的值，6.75=(00100110)2，其补数为29-6.75=(100000000)2-(00100110)2=(11011010)2，因此我们得到-6.75的补码为(11011010)2。我们可以发现其实这正是-6.75的反码值(11011001)2加1的结果，因此对于有符号的浮点数我们同样可以使用反码低位加一的方法来求得补码值，只不过对于浮点数加一的位置不在20位上，而在最低位上，在上面的-6.75((11011010)2)的例子中，加一的位置在2-4位上。
4.2 浮点数
4.2.1 浮点数的组成
与科学计数法类似，浮点数解决了整数和小数位长度固定的限制，允许表示一个非常大或非常小的数。浮点数的组成如下所示：
其中M是尾数(mantissa)，B是基数(base)，E是阶码(exponent)。在二进制中，基数B是2。
4.2.2 计算机浮点数的表示方法
本节将以32位浮点数为例，阐述浮点数在实际计算机中的表示方法。
(1) 基本版本
以十进制数228为例，228=(11100100)2=(1.11001)2⋅27。在基本版本的浮点表示法中，228的表示方法如下所示，使用高1位作为符号位，随后8位作为阶码，低23位作为尾码。
| 符号 | 阶码 | 尾数 |
|---|---|---|
| 1 bit | 8 bits | 23 bits |
| 0 | 0000 0111 | 111 0010 0000 0000 0000 0000 |
(2) 省略前导1版本
细心的话可以发现，如果采用科学计数法表示二进制，尾码的最高位（即小数点前1位）永远为1，因此在浮点数的表示中我们可以将其省略，低23位用于存储小数点后23 bits的数据。相比于第一种版本，尾码将多出一比特的精度。下面给出十进制数228的省略前导1版本32浮点数表示方法。
| 符号 | 阶码 | 尾数 |
|---|---|---|
| 1 bit | 8 bits | 23 bits |
| 0 | 0000 0111 | 110 0100 0000 0000 0000 0000 |
(3) IEEE 754版本
再细心的话还可以发现，我们目前的阶码只能表示正数。因此在IEEE 754标准中，给阶码段加了一个偏置数127。例如，对于阶码7，阶码字段的值应是7+127=134=(10000110)2。对于阶码-4，阶码字段的值应是-4+127=123=(01111011)2。下面给出十进制数228的IEEE 754版本32浮点数表示方法。
| 符号 | 阶码 | 尾数 |
|---|---|---|
| 1 bit | 8 bits | 23 bits |
| 0 | 1000 0110 | 110 0100 0000 0000 0000 0000 |
对于一些特殊的数，如0，±∞，NaN（非法值），IEEE754采用下面的方法进行表示。
| 数字 | 符号 | 阶码 | 尾数 |
|---|---|---|---|
| 0 | X | 0000 0000 | 000 0000 0000 0000 0000 0000 |
| ∞ | 0 | 1111 1111 | 000 0000 0000 0000 0000 0000 |
| -∞ | 1 | 1111 1111 | 000 0000 0000 0000 0000 0000 |
| NaN | X | 1111 1111 | 非零值 |
4.2.3 单、双精度浮点数
IEEE 754中同时规定了32位（单精度浮点数，signle-precision，signle或float）和64位（双精度浮点数，double-precision，double）浮点数表示法，具体如下所示。
| 格式 | 总位数 | 符号位数 | 阶码位数 | 小数位数 |
|---|---|---|---|---|
| 单精度浮点数 | 32 bits | 1 bit | 8 bits | 23 bits |
| 双精度浮点数 | 64 bits | 1 bit | 11 bits | 52 bits |
单精度浮点数的表示范围是±1.175494⋅10-38~±3.402824⋅1038，具有7位有效的十进制数字（2-24=10-7，24是因为采用省略前导1后，一共有23位表示小数部分，加上前导1一共有24位精度）。双精度浮点数的表示范围是±2.22507385850720⋅10-308~±1.79769313486232⋅10308，具有15位有效的十进制数字。
附录：参考
David Money Harris, Sarah L, Harris, 机械工业出版社, 数字设计和计算机体系结构
电子科技大学, Digtal Logic Circuit and System 课程课件（2018秋季）
CSDN博主leonliu06，补码原理——负数为什么要用补码表示