二进制数的运算原理与门电路实现

本文地址：https://www.cnblogs.com/faranten/p/16099916.html
转载请注明作者与出处

1 数据和表示方法

1.1 数字的表示

1.1.1 定点数

​ 在计算机中，数字分为定点数和浮点数两类，“定点”的含义为小数点的位置是固定的，“浮点”则意味着小数点的位置不固定。简单起见，定点数分为纯小数和纯整数，如果有一个数xx在计算机中的存储为xnxn−1⋯x1x0xnxn−1⋯x1x0，则

纯小数xn.xn−1⋯x1x00≤|x|≤1−2−1纯整数xnxn−1⋯x1x0.0≤|x|≤2n−1(其中xn为符号位)

整型数据就是用定点数的方式表示的。

1.1.2 原码、反码、补码、移码

​ 如果要让数据具有正负性，有多种处理方式，一种最常见的方式就是原码，它的思路就是单独留出一个二进制位（比特）来表示符号，且该位不具备权重，即对于一个真值x而言，它在计算机中的原码表示为[x]原：

[x]原=xnxn−1⋯x1x0,xn是x的符号位,xn−1⋯x1x0是|x|的二进制表示

而反码则是利用了实数轴的对称性，真值x在计算机中的反码表示为[x]反：

[x]反={xnxn−1⋯x1x0,x≥0ˉxnˉxn−1⋯ˉx1ˉx0,x≤0其中xnxn−1⋯x1x0是|x|的二进制表示

补码则是将最高位视为一个特殊的带权位，真值x在计算机中的补码表示为[x]补：

[x]补=符号位xn连接上{xn−1⋯x1x0,x≥0ˉxn−1⋯ˉx1ˉx0+12,x<0其中xn−1⋯x1x0是|x|的二进制表示

其中⇁表示对二进制中的每一位进行取反操作。上面的三个式子给出了从真值x生成机器表示的方法，下面给出从机器表示xnxn−1⋯x1x0反解出真值的方法：

原码x=(−1)xn⋅n−1∑i=02i⋅xi反码x=(−1)xn⋅n−1∑i=02i⋅(xi⊕xn)补码x=(−1)xn⋅2n+n−1∑i=02i⋅xi

其中⊕为异或运算。下面的表格给出了这三个表示方式的差别（以8个比特为例）：

计算机中存储形式	原码→真值	反码→真值	补码→真值
0000 0000	+0	+0	0
0000 0001	+1	+1	+1
0000 0010	+2	+2	+2
…	…	…	…
0111 1110	+126	+126	+126
0111 1111	+127	+127	+127
1000 0000	−0	−127	−128
1000 0001	−1	−126	−127
…	…	…	…
1111 1101	−125	−2	−3
1111 1110	−126	−1	−2
1111 1111	−127	−0	−1

可以看出，不论是什么存储方式，最高位始终可以起到标志正负的符号位作用。

​ 至于移码，这只是一个存储上的技巧而已，主要用于比较大小，真值e在计算机中的移码表示为[e]移：

[e]移=ekek−1⋯e1e0,ekek−1⋯e1e0是2k+e的二进制表示

其中e本身采用补码表示，即−2k≤e≤2k−1，则0≤e≤2k+1−1，相当于添加了一个偏置使其为正数，从硬件上来说，移码更容易直接比较大小。

1.1.2 浮点数

​ 定点数能够表示的范围是有限的，且定点数在它表示范围内的不同区域中的精度是一样的。考虑到任何数都能写为

十进制N10=M×10E二进制N2=M×2e

通过下面的定义

阶符	阶码	数符	尾数
Es	Em−1⋯E1E0	Ms	Mn−1⋯M1M0

就能表示浮点数，其中阶符和数符分别表示阶码和尾数的正负。并且可以发现，在不同区域，这样定义的浮点数表示的数字的精度是不同的，精度取决于尾数的有效位数。在实际应用中，我们用 IEEE 754 标准定义浮点数，这包括单精度 float 浮点数和双精度 double 浮点数：

31	30 - 23	22 - 0
符号位S	阶码E=e+Bias32	尾数M

63	62 - 52	51 - 0
符号位S	阶码E=e+Bias64	尾数M

​ 下面先来看浮点数的生成方式。给定一个任意的无符号浮点数

x=xnxn−1⋯x1x0.x−1x−2⋯x−m+1x−m

则通过移位，理想情况下我们能得到

x=xi.xi−1xi−2⋯x−m+1x−m×2i−n,其中xi为x二进制形式中最左侧的1

于是，理想情况下，我们将分别存储xi.xi−1xi−2⋯x−m+1x−m和i−n两个部分，不幸的是，这两个之中总可能会有一个超出能够表示的范围：

• 如果xi.⋯的总位数是超出了分配给它的位数（而i−n的机器表示表示没有超出分配给它的位数），考虑到此时总有xi=1，故只需存储.xi−1⋯，在单精度数中，这个纯小数部分最多为23位，在双精度中，这个纯小数部分最多为52位，多余的位数被截断
• 如果i−n的机器表示表示超出了分配给它的位数（单精度中为8位，双精度中为11位）（而xi.⋯的总位数没有超出分配给它的位数），有两种具体的情况：
  • 正数i−n过大，即小数点向左移动了太多还不能保证此小数点左侧只有一个1，即x=xjxj−1⋯.⋯x−m×2e（其中xj=1），此时阶码取最大二进制表示（单精度中为8个1，双精度中为11个1），这时候纯小数部分.xj−1⋯最多为23位（单精度）或52位（双精度）
  • 负数i−n过小，即小数点向右移动了太多还不能保证小数点左侧xj=1，即此时x=xj.xj−1⋯x−m×2e（其中xj=0），此时阶码取最小二进制表示（单精度中为8个0，双精度中为11个0），这时候纯小数部分.xj−1⋯最多为23位（单精度）或52位（双精度）
• 如果两部分都超过了各自的最大位数，这时优先保证量级正确，即先处理情况二（阶码超出），之后再处理情况一（小数部分超出）

如果阶码的机器表示没有超出分配给它的位数，则这种数称为规格化的数，它的特点是尾数M有隐含的1，偏置值为Bais32=127或Bais64=1023，阶码值为e=E−Bais，且阶码段既不是全1也不是0（因为全1和全0留给了后面的情况）。如果阶码的机器表示超出了分配给它的位数，则这种数称为非规格化数，它的特点是尾数M没有隐含的1，阶码段为全1或全0，当阶码段为全0时，阶码值e=1−Bais（之所以不是0−Bais是为了保证非规格化数和规格化数的平滑过渡），当阶码段为全1时，它的含义后面叙述。

​ 下面的表格以8位比特为例说明了 IEEE 754 浮点数定义的转换方法和具体含义：

描述	位表示	e	E	2E	f	M	2E×M	V	十进制
0	0 0000 000	0	−6	164	08	08	0512	0	0.0
最小非规格化数	0 0000 001	0	−6	164	18	18	1512	1512	0.001953
	0 0000 010	0	−6	164	28	28	2512	1256	0.003906
	0 0000 011	0	−6	164	38	38	3512	3512	0.005859
	⋯
最大非规格化数	0 0000 111	0	−6	164	78	78	7512	7512	0.013672
最小规格化数	0 0001 000	1	−6	164	08	88	8512	164	0.015625
	0 0001 001	1	−6	164	18	98	9512	9512	0.017578
	⋯
	0 0110 110	6	−1	12	68	148	1416	78	0.875
	0 0110 111	6	−1	12	78	158	1516	1516	0.9375
	0 0111 000	7	0	1	08	88	88	1	1.0
	0 0111 001	7	0	1	18	98	98	98	1.125
	0 0111 010	7	0	1	28	108	108	54	1.25
	⋯
	0 1110 110	14	7	128	68	148	17928	224	224.0
最大规格化数	0 1110 111	14	7	128	78	158	19208	240	240.0
正无穷大	0 1111 000	-	-	-	-	-	-	+∞	-
负无穷大	1 1111 000	-	-	-	-	-	-	−∞	-
非数 NaN	0/1 1110 非0	-	-	-	-	-	-	-	-

可以看出，在不同区域，这样定义的浮点数表示的数字的精度是不同的。

1.2 文字的表示

1.2.1 字符与字符串

​ 字符与字符串采用 ASCII 码进行存储，它规定最高位为0，余下的7位可以给出128个编码，包括大小写英文字母、数字符、运算符和标点符号以及一些控制码。常见的有：

• b7b6b5b4 b3b2b2b1=0011 0000=(48)10=(30)16开始的10个编码表示数字符0到9
• b7b6b5b4 b3b2b2b1=0100 0001=(65)10=(41)16开始的26个编码表示大写字母
• b7b6b5b4 b3b2b2b1=0110 0001=(97)10=(61)16开始的26个编码表示小写字母

值得一提的是，此处的数字符与上面提到的数据的存储不是一回事，上面的数据存储的基于二进制存储的（有权码），而此处的数字符是直接基于十进制存储的（无权码）。

​ 有两种存储方式：大端法（big endian）和小端法（little endian）。大端法的最高有效字节在最前面，小端法的最低有效字节在最前面。假设变量int a=0x01234567，则大端法（第一个表格）和小端法（第二个表格）形式分别为（按字节编地址）：

	0x100	0x101	0x102	0x103
⋯	01	23	45	67	⋯

	0x100	0x101	0x102	0x103
⋯	67	45	23	01	⋯

一切跨越多个字节的数据类型都需要考虑大小端法才能确定具体的存储顺序。其中每个字节内部存储的两个数字顺序是固定的，一个字节的8个比特位被切分为两个4比特位存储数据，将0到9这10个数字编码成4的方法有很多，比如 8421BCD 码、格雷码（及其他循环码）等等。

1.2.2 汉字

​ 汉字在计算机中的存储分为三种情况：

• 输入时（汉字的输入编码）：
  • 数字编码：常用国标区位码，用数字串代表一个汉字输入。区位码是将国家标准局公布的6793个汉字分为94个区，每个区分为94位，实际上把汉字表示成二维数组，每个汉字在数组中的下标就是区位码。区码和位码各两位十进制数字，因此输入一个汉字需按键四次。例如“中”字位于第54区48位，区位码为 5448
  • 拼音码：拼音码是以汉语拼音为基础的输入方法，但汉字同音字太多，输入重码率很高，因此按拼音输入后还必须进行同音字选择
  • 字形编码：字形编码是用汉字的形状进行的编码。全部汉字的部件和笔画是有限的，把汉字的笔画部件用字母或数字进行编码，按笔画的顺序依次输入，就能表示一个汉字。例如五笔字型编码是最有影响的一种字形编码方法
• 存储时（汉字内码）：汉字内码是用于汉字信息的存储、交换、检索等操作的机内代码，一般采用2字节表
  示。英文字符的机内代码是七位的 ASCII 码，当用1字节表示时，最高位为0。为了与英文字符能相互区别，汉字机内代码中2字节的最高位均规定为1。有些系统中字节的最高位用于奇偶校验位，这种情况下用3字节表示汉字内码
• 输出时（汉字字模码）：字模码是用点阵表示的汉字字形代码，它是汉字的输出形式。简易型汉字为16×16点阵，提高型汉字为24×24点阵、32×32点阵甚至更高。因此字模点阵所占存储空间很大。16×16点阵的汉字要占用16×16÷8=32字节，国标两级汉字要占用256K字节。因此字模点阵只能用来构成汉字库，而不能用于机内存储。当显示输出或打印输出时才检索字库，输出字模点阵，得到字形。

2 定点运算

2.1 定点加减法（补码）

​ 对于定点数来说，加法和减法具有统一性，原因是因为

[x]补+[y]补=[x+y]补[x]补−[y]补=[x−y]补

第一个式子可以分为四种情况来证明：

• x≥0 and y≥0：相加为正数，因为正数的原码补码相同，则有[x]补+[y]补=x+y=[x+y]补
• x≥0 and y<0：相加可能为正可能为负，根据补码的定义有[x]补+[y]补=x+y+2n+1=[x+y]补
• x<0 and y≥0：和第二种情况一样
• x<0 and y<0：相加结果为负，根据补码定义有[x]补+[y]补=x+y+2n+1+2n+1=[x+y]补

而第二个式子的证明如下：因为[y]补=[x+y]补−[x]补且[−y]补=[x+(−y)]补−[x]补=[x−y]补−[x]补，将此两式相加得到

[y]补+[−y]补=[x+y]补−[x]补+[x−y]补−[x]补=[x+y]补+[x−y]补−[x]补−[x]补=[(x+y)+(x−y)]补−[x+x]补=[x+x]补−[x+x]补=0

因此−[y]补=[−y]补，所以[x]补−[y]补=[x]补+[−y]补=[x−y]补。

​ 补码的加法是在取模运算之下所做的运算，也就是说，超出应有位数的部分应当被舍弃。下面通过两个例子来说明补码加减法的具体操作：

例 已知x1=+(14)10=+(1110)2，x2=−(13)10=−(1101)2，求x1+x2

首先求出[x1]补=0 1110以及[x2]补=1 0011，相加得1 0 0001，丢弃第一位，得0 0001，即为+1。

例 已知x1=+(13)10=+(1101)2，x2=+(6)10=+(0110)2，求x1−x2

首先求出[x1]补=0 1101以及[−x2]补=1 1010，相加得1 0 0111，丢弃第一位，得0 0001，即为+7。

2.2 溢出的概念和检测方法

​ 当相加的两数都比较大的时候，有可能出现加和之后的结果大于该范围能表示的最大数的情况，该情况的直观体现为

正数+正数→负数or负数+负数→正数

需要注意的是，负数与正数相加（正数与负数相加）的不可能超出范围的。下面先看两个例子，再来分析溢出的原理和检测方法：

例 已知x1=+(11)10=+(1011)2，x2=+(9)10=+(1001)2，求x1+x2

首先求出[x1]补=0 1011以及[x2]补=0 1001，相加得1 0100，即为−12，这显然是荒唐的。

例 已知x1=−(13)10=−(1101)2，x2=−(11)10=−(1011)2，求x1+x2

首先求出[x1]补=1 0011以及[x2]补=1 0101，相加得1 0 1000，丢弃第一位，得0 1000，即为+8，这显然是荒唐的。

​ 溢出在区域上分为正溢（在正数范围发生的溢出）和负溢（在负数范围发生的溢出），在方向上分为上溢出（向大方向发生的溢出）和下溢出（向小方向发生的溢出），对于浮点数而言，一共有四种溢出情况：

不能表示	最大规格化数	⋯	最小非规格化数	不能表示	0	不能表示	最小非规格化数	⋯	最大规格化数	不能表示
负下溢	未溢出	⋯	未溢出	负上溢	0	正下溢	未溢出	⋯	未溢出	正上溢

而对于整型而言，正溢和上溢是相同的、负溢和下溢是相同的。

​ 对整型而言，溢出的检测办法有两个。其一是变形补码法，例子为：

例 已知x1=+(12)10=+(1100)2，x2=+(8)10=+(1000)2，求x1+x2

首先求出[x1]变补=00 1100以及[x2]变补=00 1000，相加得01 0100，由于符号位为01，故发生了正溢出。

例 已知x1=−(12)10=−(1100)2，x2=−(8)10=−(1000)2，求x1+x2

首先求出[x1]变补=11 0100以及[x2]变补=11 1000，相加得1 10 1100，丢弃第一位，得10 1100，由于符号位为10，故发生了负溢出。

​ 那么我们可以知道，变形补码检测溢出的法则为：

• 如果结果的两位符号位相同，则未发生溢出
• 如果结果的两位符号位不同，则01意味着正溢出，10意味着负溢出

该逻辑可用异或门实现，受此启发，我们得到溢出的另一种检测方法：单符号法

• 当最高有效位产生进位而符号位无进位时，产生正溢
• 当最高有效位无进位而符号位有进位时，产生负溢

下面用两个例子说明这一点：

例 已知x1=+(12)10=+(1100)2，x2=+(8)10=+(1000)2，求x1+x2

首先求出[x1]补=0 1100以及[x2]补=0 1000，相加得1 0100，此时最高有效位产生了给符号位的进位1，而符号位没有产生溢出的进位1，因此属于正溢。

例 已知x1=−(12)10=−(1100)2，x2=−(8)10=−(1000)2，求x1+x2

首先求出[x1]补=1 0100以及[x2]补=1 1000，相加得1 0 1100，此时最高有效位没有产生给符号位的进位1，而符号位却产生了溢出的进位1，因此属于负溢。

2.3 定点加减法（补码）的门电路

​ 定点加减法最简单的实现是基于一位全加器的连接，下图 (a) 为全加器的门电路（Ai和Bi为加数，Ci为来自上一位的进位），图 (b) 为行波进位的加法减法器：

​ 下面来分析延迟。在门电路分析中，我们选定信号通过与门或者或门的时间为T，且设经过异或门的时间为3T，则对于单个全加器而言，产生加和Si的延迟为3T+3T=6T、产生进位Ci+1的延迟为3T+T+T=5T。对于较为复杂的门电路来说，要计算它的延迟就是要找到其中最长的时间链，对于上图的行波进位的加法减法器来说，最长的时间链就是从A0和B0输入经过n次进位最终产生溢出标志的链路，该链路所花费的时间为

3T(对B0预处理)+3T(A0和B0的异或门)+n⋅2T(n次进位)+3T(产生溢出符号的异或门)=(2n+9)T

可以看出，这种方式的加法在进位上花费了大量的时间，下面来看先行加法的设计思路，该方法加速了加法过程。令Pi=Ai⊕Bi、Gi=AiBi，则进位为Ci+1=Gi+PiCi，那么对于连续的加法而言：

C1=G0+P0C0C2=G1+P1C1=G1+P1G0+P1P0C0C3=G2+P2C2=G2+P2G1+P2P1G0+P2P1P0C0C4=G3+P3C3=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0C0⋯

这样一直推下去，理论上说，任意位数的加法中的任意一个进位都可以根据直接输入的数值计算出来（而不必依赖进位），根据多方面的考虑，常常以四位为一组，组内进行超前加法（先行加法、并行进位），而组之间使用传统的进位加法（串行进位、即C5依赖于进位而不是直接计算得到），每个这样的单元称为四位先行进位部件（Carry Look Ahead or CLA），每个这样的单元延迟为2T（因为经过了一次多重与门和一次多重或门，且不考虑Pi和Gi的生成延迟）。对于两个16位数的不考虑溢出检测的加法来说，使用四个这样的单元就能完成加法过程，门电路如下图所示：

左侧的虚线框的功能是求出所有的Pi与Gi，中间虚线框的功能是进行串行进位操作，右侧的虚线框的功能是根据Ai、Bi和Ci求出加和结果Si。该结构中最长的时间链为从A0和B0进去、生成P0、再经过先行进位与传统进位到达最上面的 CLA、再经过求和操作得到最终的结果，延迟为

3T(生成P0的异或门)+2T(产生C4的时间)+2T(产生C8的时间)+2T(产生C12的时间)+2T(产生C16的时间)+3T(最后生成S15的异或门的时间)=14T

注意，最后生成S15的时候只经过了一个异或门，因为S15=A15⊕B15⊕C15中的第一个异或门已经在更早的时候经过了。如果采用完全串行进位，则延迟为

3T(对B0预处理)+3T(A0和B0的异或门)+(16−1)⋅2T(15次进位)=(2⋅15n+9)T=39T

可以看到延迟有较大的差异。这里加法不考虑溢出检测，故不论是经由 CLA 实现的加法还是传统的串行加法，都没有考虑溢出检测所花费的时间（因此传统串行加法中的最后一次进位没有必要）。在 CLA 实现的加法中如果考虑溢出检测，因为溢出检测经过一个异或门（即C16⊕C15）的延迟也为3T，因此总延迟不变。

2.4 定点乘法（原码）

​ 由于原码与真值极为相似（只差一个符号），而乘积的符号又可以通过两数符号的异或得到，因此，对于原码的乘法而言，只需要忽略符号位进行典型的二进制乘法，最后在结果中单独添加一个符号位即可，下面通过一个例子来说明：

例 已知x=−0.1110，y=−0.1101，求[x⋅y]原

首先求出[x]原=1.1110以及[y]原=1.1101，然后取出不含符号位的1110和1101两部分相乘，得到10110110，然后在前面加上符号位，得到[x⋅y]原=0.10110110。

2.5 定点乘法（原码）的门电路

​ 下面讨论不带符号（即无符号数，原码中不含符号位的部分的乘法也符合此情况）的阵列乘法器，不带符号的阵列乘法器的门电路为：

被加数为一系列的aibj，接下来的阵列乘法器将对这些被加数进行对应的加法，阵列乘法器为：

以上是五位二进制数乘以五位二进制数的阵列器，斜线表示来自上一级的进位输入，最后输出的结果为p9p8⋯p1p0。对于这个器件来说，最长的链路为从a4b0与a3b1的全加器、到a2b2的全加器、到a1b3的全加器、到a0b4的全加器、到最后一行最右侧的全加器、再经过3次进位到最后一行最左侧的全加器、最后输出p8的链路，所以延迟为

T(生成被加数的时间)+(n−2)⋅6T(竖直向下的传递时间)+5T(沿斜线向最后一行的进位时间)+(n−2)⋅2T(最后一行内部经过n−2次进位到达最左侧全加器的时间)+3T(生成p8的一个异或门时间)=(8n−7)T,33T(上述n=5时)

​ 如果我们输入的是两个原码，那么根据上面的不带符号的阵列乘法器，我们已经计算得到了不含符号位的乘法结果（比如输入−3和5时，得到的是15），如果要使得到的结果也是补码表示，那么在所得结果之前加上两个乘数的符号位的异或即可。

2.6 定点乘法（补码）

​ 对于补码形式的数而言，它的乘法规则不再显然，通常我们先将这两个数转换为原码形式（通过后面所述的求补器实现），再按照原码的定点乘法规则（符号位单独考虑）进行乘法，在得到的乘法结果前面加上单独考虑的符号位，得到了原码表示的结果。如果想让最后的结果以补码形式表示，则只需要在最后使其通过求补器即可。下面通过两个例子说明该思路的具体操作过程：

例 已知x=+(13)10=+(1101)2，y=+(11)10=+(1011)2，求x⋅y

首先求出[x]原=0 1101以及[y]原=0 1011，然后将不含符号的1101和1011相乘，得1000 1111，两个符号位单独异或，得到积的符号位为0⊕0=0，则结果为[x⋅y]原=0 1000 1111，即x⋅y=+(1000 1111)=143。

例 已知x=+(3)10=+0011，y=−(11)10=−(1011)2，求x⋅y

首先求出[x]原=0 0011以及[y]原=1 1011，然后将不含符号的0011和1011相乘，得100001，两个符号位单独异或，得到积的符号位为0⊕1=1，则结果为[x⋅y]原=1 100001，即为x⋅y=−(100001)=−33。

​ 上面这种将补码转换为原码的方法，在思路上很简便，将补码的情况转变成了我们在2.4节中讨论过的情况。下面介绍直接使用补码进行乘法的思路，该思路不需要转换为原码，一定程度上减少了出错的可能性。

​ 补码不能直接参与乘法的原因是：符号位的含义与后面的一般数码没有统一性，参考资料中唐朔飞著作中提到了当两个乘数的补码形式的符号任意时的Booth算法，此处略去不谈。

2.7 定点乘法（补码）的门电路

​ 之前现在我们已经讨论了原码的乘法器实现，如果试图计算的是两个补码的乘法结果，那么对于输入的补码而言，根据2.6节的内容，先将这两个数转换为原码形式（通过后面所述的求补器实现），再按照原码的定点乘法规则（符号位单独考虑）进行乘法，在得到的乘法结果前面加上单独考虑的符号位，得到了原码表示的结果。如果想让最后的结果以补码形式表示，则只需要在最后使其通过求补器即可，门电路如下所示：

其中求补器的门电路为：

当E=1时进行求补运算，当E=0时输入和输出一样。该器件实现的思路为：从数的最右端a0开始，由右向左，直到找出第一个1，例如ai=1(0≤i≤n)。这样，ai以右的每一个输入位，包括ai自己，都保持不变，而ai以左的每一个输入位都求反。鉴于此，横向链式线路中的第i扫描级的输出Ci为1的条件是：第i级的输入位ai=1，或者第i级链式输入（来自右起前i–1级的链式输出）Ci–1=1。另外，最右端的起始链式输入C–1必须永远置成0。如果我们有n+1=5位的输入，由于符号位单独考虑，则该求补器中最长的链路为：从C−1开始、经过(n+1)−1次进位、再经过一个与门和一个异或门输出a∗3的链路，因此延迟为

((n+1)−1)⋅2T(n−1次进位)+2T(与门)+3T(异或门)=(2n+5)T,13T(上述n+1=5时)

注意，和前面的假设不同的是，这里假设与门与或门延迟为2T，异或门延迟为3T。

​ 最后指出，由于补码的唯一性，我们既可以对补码求补得到原码（符号位单独考虑），也可以对补码求补得到原码（符号位单独考虑）。

2.8 定点除法（原码）

​ 先来讨论原码的除法。由于在二进制除法中商数只可能是1，故余数减去一倍的除数只有两种情况：够减（减法结果大于零，此时令商为1）与不够减（减法结果小于零，此时令商为0），在实际应用中，有两种具体的思路：

• 恢复余数法：当不够减的时候，恢复余数，并上商为0，进行后续的操作，这种思路最后得到的余数是准确的
• 加减交替法：够减则下一步进行减法、不够减则下一步进行加法，这种思路最后得到的余数可能需要纠正

为了避免不够减时返回去重新计算，我们采用加减交替的思路，它的原理由下式保证

若r′i=2ri−1−y>0则ri=r′i且r′i+1=2ri−y=2r′i−y若r′i=2ri−1−y<0则ri=r′i+y且r′i+1=2ri−y=2r′i+y

其中ri−1是当前的余数（即将作为被减数，减数为除数y），r′i=2ri−1−y可能是新的余数（如果该数大于零则是，小于零则不是）（大于零则令商为1，小于零则令商为0），ri是真的新的余数（但我们只关心最后的结果商，而不关心这种中途生成的余数），从上式可以看出，下一级的可能余数r′i+1的生成方式取决于当前的可能余数r′i（减去除数y或加上除数y），如果r′i+1>0则下一位商置为1，如果r′i+1<0则下一位商置为0，如此不断进行下去，直到出现某个rj=0或者到达最大精度。

​ 上面讨论的原码除法，适用于任何原码之间的除法（正数与正数、正数与负数、负数与正数、负数与负数，中间两种的符号位单独处理），虽然称为原码乘法，但运算中涉及到的加减法仍然是补码的，所谓“原码”仅是指参与除法的两个数需要先取绝对值才能才与运算，至于商数的符号位则单独确定，这和原码乘法是类似的，但不同之处在于，原码乘法中不涉及到减法而原码除法涉及到减法。

​ 我们在此只讨论了原码（即无符号数，原码中不含符号位的部分的乘法也符合此情况）的除法原理，有符号数（比如补码）的情况后面再谈。后面的例子说明这一点。下面通过两个例子说明原码定点除法的实现过程：

例 已知x=+(9)10=+(1001)2，y=+(11)10=+(1011)2，求x÷y

首先求出[x]原=0 1001以及[y]原=0 1011，然后取绝对值（即所谓的无符号数）0 1001和0 1011依次进行下面的操作：

i	被除数	除数	2r′i−1	r′i=2r′i−1±y	商
1	0 1001	0 1011	被除数	被除数−0 1011=0 1001+1 0101=1 1110<0	0
2	0 1001	0 1011	1 1100	1 1100+0 1011=1 0 0111，丢弃第一位得0 0111>0	1
3	0 1001	0 1011	0 1110	0 1110−0 1011=1 0 0011，丢弃第一位得0 0011>0	1
4	0 1001	0 1011	0 0110	0 0110−0 1011=1 1011<0	0
5	0 1001	0 1011	1 0110	1 0110+0 1011=1 0 0001，丢弃第一位得0 0001>0	1
⋯	0 1001	0 1011	⋯	⋯	⋯

然后对符号位单独异或0⊕0=0，因此[商]原=0.1101（第一位是符号位）。

例 已知x=+(9)10=+(1001)2，y=−(11)10=−(1011)2，求x÷y

首先求出[x]原=0 1001以及[y]原=1 1011，然后取绝对值（即所谓的无符号数）a=0 1001和b=0 1011依次进行下面的操作：

i	被除数a	除数b	2r′i−1	r′i=2r′i−1±y	商
1	0 1001	0 1011	被除数	被除数−0 1011=0 1001+1 0101=1 1110<0	0
2	0 1001	0 1011	1 1100	1 1100+0 1011=1 0 0111，丢弃第一位得0 0111>0	1
3	0 1001	0 1011	0 1110	0 1110−0 1011=1 0 0011，丢弃第一位得0 0011>0	1
4	0 1001	0 1011	0 0110	0 0110−0 1011=1 1011<0	0
5	0 1001	0 1011	1 0110	1 0110+0 1011=1 0 0001，丢弃第一位得0 0001>0	1
⋯	0 1001	0 1011	⋯	⋯	⋯

然后对符号位单独异或0⊕1=1，因此[商]原=1.1101（第一位是符号位）。

​ 下面来看纠正余数的问题。采用加减交替法的原码除法的一个小缺陷就是最后得到的余数可能不是真正的余数（但最后得到的商数一定是真的商数）。原码除法的余数纠正并不是明晰的，因为它涉及到原码和补码的转换，我们将在后面补码除法除法中详细说明余数纠正的一般规则。

2.9 定点除法（原码）的门电路

​ 从上面的内容，我们不难发现，原码的定点除法具有下面的特征：

• 在形式上永远是正数和正数的除法（因为取了绝对值）
• 被除数不需要在计算过程中保存，除数需要在计算过程中保存并向下一级传递
• 每次计算的可能余数r′i在参与下一级运算之前需要左移一位（该操作模拟的是真实除法过程中在余数后面加上一个0的过程）
• 由于通过加减交替的思路实现，故内部应该整合一个进行补码加减法的门电路

根据上面的特征，我们可以设计出可控加法减法（CAS）单元如下：

在计算的一开始，Ai为被除数的某一位，在后面的过程中，Ai为2r′i的某一位，P=0则进行加法运算，P=1则进行减法运算，Bi为除数的某一位（将保持不变向下传递），Ci为来自上一级的进位（进行加法时C−1=0，进行减法时C−1=1），Si为加和结果，Ci+1为进位结果。下图展示了如何将这些单元组合起来构成4位除4位的阵列除法器：

（最后得到的是不含符号位的商）。其中，沿着斜线输入的0y3y2y1为除数，沿着竖线输入的0x6x5x4x3x2x1为被除数。对于第一行而言，第一次执行的操作为减法，故输入P=1（且第一行最右侧输入的C−1=P=1），第一行最左侧的进位输出用于判断可能余数的正负（由此决定下一次进行加法还是减法），如果进位为0则说明可能余数为负数（此时令商为0且下一次进行加法），如果进位为1则说明可能余数为正数（此时令商为1且下一次进行减法）。从例11也可以看出，正数总是通过丢弃最高位才得到的，这实际上由更深入的原理来保证。在严格的4位除4位的除法当中，被除数0x6x5x4x3x2x1=0x6x5x4000，在除法向下推进的过程中，上一次得到的可能余数的最高位不再参与运算，并在最低位引入x3或x2或x1，这满足了可能余数r′i在参与下一级运算之前需要左移一位的要求。

​ 现在来分析延迟。在上述所示的4位除4位的阵列除法器中，我们记真正有效的位数3为n，则被除数有效部分为2n，除数有效部分为n，阵列除法器一共有(n+1)2个 CAS 单元。该阵列除法器中最长的链路为：从P=1输入开始，经过每一行的每一次进位再进入下一行、直到最后生成最后一个商p1的时间，因此延迟为

(n+1)2⋅3T((n+1)2次进位时间)=3(n+1)2T,48T(上述n=3时)

2.10 定点除法（补码）

​ 现在略去具体的推导（详见参考资料中唐朔飞著作），直接给出补码除法的一般规则：

[x]补与[y]补	商	[R]补与[y]补	上商	下一步
同号	正数	同号，表示够减	1	+[−y]补
同号	正数	异号，表示不够减	0	+[y]补
异号	负数	异号，表示够减	0	+[y]补
异号	负数	同号，表示不够减	1	+[−y]补

下面通过两个例子加以说明：

例 已知x=−1001，y=+1101，求x÷y

首先求出[x]补=1 0111以及[y]补=0 1101，计算过程如下：

i	[x]补	[y]补	2r′i−1	r′i=2r′i−1±y	商
1	1 0111	0 1101	被除数	1 0111+0 1101=1 0 0100，丢弃第一位得0 0100与[y]补同号	1
2	1 0111	0 1101	0 1000	0 1000−0 1101=1 1011，与[y]补异号	0
3	1 0111	0 1101	1 0110	1 0110+0 1101=1 0 0011，丢弃第一位得0 0011与[y]补同号	1
4	1 0111	0 1101	0 0110	0 0110−0 1101=1 1001，与[y]补异号	0
⋯	1 0111	0 1101	⋯	⋯	⋯

因此[x÷y]补=1.010，故x÷y=−0.110。

例 已知x=+1001，y=+1101，求x÷y

首先求出[x]补=0 1001以及[y]补=0 1101，计算过程如下：

i	[x]补	[y]补	2r′i−1	r′i=2r′i−1±y	商
1	0 1001	0 1101	被除数	0 1001−0 1101=1 1100，与[y]补异号	0
2	0 1001	0 1101	1 1000	1 1000+0 1101=1 0 0101，丢弃第一位得0 0101与[y]补同号	1
3	0 1001	0 1101	0 1010	0 1010−0 1101=1 1101，与[y]补异号	0
4	0 1001	0 1101	1 1010	1 1010+0 1101=1 0 0111，丢弃第一位得0 0111与[y]补同号	1
⋯	0 1001	0 1101	⋯	⋯	⋯

因此[x÷y]补=0.101，故x÷y=+0.101。

​ 下面来看余数的纠正：

• 如果当前上商为1，则当前余数就是真余数
• 如果当前上商为0，则当前余数需要加上[y]补才是真余数

来看例子：

• 上面第一个例，i=4时，上商0，真余数为0 0110
• 上面第一个例，i=3时，上商1，真余数为0 0011
• 上面第二个例，i=4时，上商1，真余数为1 1010
• 上面第二个例，i=3时，上商0，真余数为0 1010

2.11 定点除法（补码）的门电路

​ 结构和原码的除法门电路一样，只不过涵盖了符号位，且检测上商的时候不仅需要可能余数[R]补的符号位、而且需要除数[y]补，这两者同号则上商1，否则上商0。另外，原码除法必定是正数除以正数，所以第一步一定进行的是减法，但在补码除法中如果被除数和除数同号则第一步进行减法、否则进行加法，所以首先输入的P可能是1（进行减法）、也可能是0（进行加法）。

5 浮点运算

5.1 浮点加减法

​ 完成浮点加减法的大致过程分为四步：

• 0操作数检查
• 比较阶码大小并完成对阶
• 尾数进行加减运算
• 结果规格化并进行舍入处理

接下来结合下图说明具体过程：

上图显示的是x±y的操作过程。在对阶操作中，总是小阶向大阶对齐，比如x=1.0002×2−1，y=−1.1102×2−2，则y应该转成y=−0.1112×2−1。注意，在此对阶过程中可能出现尾数丢失的问题，因此要进行所谓的舍入处理（后面叙述）。在对阶完成之后，进行加减法，然后对尾数进行规格化处理，此时在规格化时也涉及到了舍入处理，现在来讨论这个处理的具体内容。舍入处理发生在对阶和向右规格化时，这样，被右移的尾数的低位部分就会被丢掉，从而造成一定误差，所以进行舍入处理，常见的舍入处理有下面几种：

• 就近舍入：就是”四舍五入“。例如，若被舍弃的五位二进制位为10010，则丢弃这五位之后的最低二进制位因该加一；若被舍弃的四位二进制位为0111，则丢弃这四位之后的最低二进制位保持不变
• 朝0舍入：即朝数轴原点方向舍入，就是简单的截尾。无论尾数是正数还是负数，截尾都使取值的绝对值比原值的绝对值小。这种方法容易导致误差累积
• 朝+∞舍入：对正数来说，只要多余位不全为0则向最低有效位进1；对负数来说，则是简单的截尾
• 朝−∞舍入：对负数来说，只要多余位不全为0则向最低有效位进1；对正数来说，则是简单的截尾

同时，在最后对结果进行规格化的过程中，阶码可能会溢出，常见的阶码溢出和处理手段如下所示：

• 阶码上溢：超过了阶码可能表示的最大值的正整数值，一般将其认为是+∞和−∞
• 阶码下溢：超过了阶码可能表示的最小值的负指数值，一般将其认为是0

当然，在尾数进行加减法运算的时候，也可能会溢出，但是这种溢出可能是不致命的，常见的尾数溢出种类和处理手段如下所示：

• 尾数上溢：两个同符号尾数相加产生了最高位向上的进位，要将尾数右移，阶码增1来重新对齐
• 尾数下溢：在将尾数右移时，尾数的最低有效位从尾数域右端流出，要进行舍入处理

5.2 浮点乘除法

​ 浮点乘数法的计算过程比浮点加减法的计算过程从概念上来说简单许多，大体上分为六个步骤：

• 0操作数检查
• 阶码加减操作
• 尾数乘除操作
• 结果规格化
• 舍入处理
• 确定积的符号

上面的步骤暗示出此处的尾数乘法实际上是按照原码进行的（因为符号位单独处理），也就是用到了2.5节中叙述的原理。当然，在此过程中也要时刻注意是否有溢出问题。浮点乘除法的整个流程如下图所示：

参考资料

• 白中英，戴志涛，《计算机组成原理（第六版）》，科学出版社，2019
• 白中英，杨春武，《计算机组成原理：题解、题库与试验（第三版）》，科学出版社，2001
• 唐朔飞，《计算机组成原理（第二版）》，高等教育出版社，2008
• Randal E. Bryant, David R. O’Hallaron, Computer Systems - A Programmer’s Perspective 3 Edi Global Edition, Pearson, 2016
• David A. Patterson, John L. Hennessy, Computer Organization and Design: The Hardware/Software Interface 5 Edi, Morgan Kaufmann, 2013