笔记 | 计算机系统基础：02-逻辑运算电路

零. 课程要点：

• 了解基础逻辑电路
• C语言中的各类运算
• 判断溢出与数据舍入

如果没学过基础逻辑电路，应该是有专门的一门课《数字逻辑电路》，那门课里有更详细的介绍。因为比较注重逻辑推理，据大学的数电老师说，自从教了这门课，反正他打桥牌就没怎么输过。在计算机系统基础这门课里只是引用一些逻辑部件，更重要的是理解C语言中各类运算是怎么通过电路实现的，由此可能存在怎样的溢出问题，这才是我们学习的重点。

另外，推荐大家一本书《编码：隐匿在计算机软硬件背后的语言》，可以看成是“如何一步步搭建一台计算机”，但是却一点都不晦涩难懂，非常生动有趣哦。

一. 数字逻辑电路

1. 与门，或门，非门，异或门

   
   门电路

2. 多路选择器

   
   多路选择器
3. 一位加法器（全加器）
   低位进位为C_in，和为F，高位进位为C_out
   一位加法器
4. n位加法器
   由n个全加器构成，例：A=1001，B=1100，则F=0101，C_out=1
   n位加法器能实现无符号的整数加，但无法用于带符号整数加，无法判断是否溢出
   n位加法器
5. n位带标准加法器
   溢出标志OF=C_nC_n-1
   进位/借位标志CF=C_outC_in
   符号标志SF=F_n-1
   零标志ZF=1当且仅当F=0
   n位带标志加法器
6. n位整数加/减运算器
   [A-B]_补 = [A]_补 + [-B]_补 = [A]_补 + + 1
   n位整数加减运算器
7. 算术逻辑部件（ALU）
   实现基本算术运算与逻辑运算，核心电路是带标志加法器，操作控制端ALU_op决定操作的类型。
   ALU

二. C语言中的运算

• 算术运算：无符号数、带符号数、浮点数的加减乘除余运算。
• 按位运算：按位与，或，取反，异或，主要用于“掩码”操作。
• 移位运算：逻辑左/右移，算术左/右移，主要用于提取部分信息，或扩大/缩小2的倍数。
• 逻辑运算：与，或，非。主要用于关系表达式。
• 位扩展和位截断运算：主要用于类型转换。

& 如何判断逻辑移位还是算术移位，怎么移位？

从运算符无法区分，由X的类型决定：

• 若X为无符号数，则为逻辑移位。
  a. 逻辑左移：高位移出，低位补0，若高位移出的是1，则发生溢出！如：197 = 1100 0101 << 2 = 0001 0100 = 20。这是因为8位无符号数可以表示0~255，高位为1，表示数值大于等于128，左移代表乘上2的倍数，超过了最大可表示范围，所以结果肯定是溢出的。
  b. 逻辑右移：低位移出，高位补0，不会溢出，但可能发生有效数据丢失。197 = 1100 0101 >> 1 = 0110 0010 = 98，精确的值应该是98.5，这里发生了有效数据的丢失。

• 若X为带符号数，则为算术移位。
  a. 算术左移：高位移出，低位补0，若移出的位不等于新的符号位，则发生溢出！如：-81 = 1010 1111 << 1 = 0101 1110 = 94。扩大和缩小倍数不应该改变符号位，所以符号位发生了变化，结果肯定是溢出的。
  b. 算术右移：低位移出，高位补符，不会溢出，但可能发生有效数据丢失。如：-81 = 1010 1111 >> 1 = 1101 0111 = -41，精确的值应该是40.5，这里发生了有效数据的丢失。

& 类型转换时如何进行位扩展和位截断？

• 位扩展：短转长
  a. 无符号数：0扩展，如：-32768 = 0x80 00 -> 0x00 00 80 00
  b. 带符号数：符号扩展，如：-32768 = 0x80 00 -> 0xFF FF 80 00
  想想为什么带符号数位扩展要进行符号扩展？我们求负数补码对应的真值时，从右往左第一个1之后按位取反，所以符号扩展不影响真值。

• 位截断：长转短
  强行将高位丢弃，可能发生溢出。如：int i = 32768 = 0x00 00 80 00，则(short) i = 0x80 00 = -32768。

& 整数加/减运算中的溢出判断

无符号数和带符号数加减运算都用以下部件完成：

n位整数加减运算器

• 无符号加法溢出判断条件：进位标志CF=C_outC_in=1
  做加法操作时，C_in=0，所以CF=C_out0=C_out，所以对于无符号数加法，只需要看最高位是否产生进位。也确实如此，两个无符号数相加，最高位进位了，说明和超过了最大可表示范围（即溢出），但由于位数有限，所以这个进位被舍弃了，值反而变小了，也就是产生了溢出。如：156 + 123 = 1001 1101 + 0111 1011 = 0001 1000 = 24 ( = 279 - 255)。

• 带符号加法溢出判断条件：溢出标志OF=C_nC_n-1=1
  最高位的进位和次高位的进位不同时则产生溢出，或者说两个加数的符号位相同但与和符号位不同，只是这个表达式看起来不是太好理解。我们分类来讨论一下：
  a. 一个正数和一个负数相加，肯定不会溢出。最高位相加肯定是1，如果次高位进位C_n-1为1，那么最高位也要向前进位，因此OF=11=0，同理如果次高位进位C_n-1为0，那么最高位也无需向前进位，因此OF=00=0，都不会产生溢出。
  b. 两个正数相加，最高位都是0，那么C_n肯定是为0，发生溢出的情况只有C_n-1为1，即OF=01=1，此时符号位改变了，结果确实产生了溢出。如：107 + 46 = 0110 1011 + 0010 1110 = 1001 1001 = -103。
  c. 两个负数相加，最高位都是1，那么C_n肯定是为1，发生溢出的情况只有C_n-1为0，即OF=10=1，此时符号位改变了，结果确实产生了溢出。-107 + (-46) = 1001 0101 + 1101 0010 = 0101 0111 = 87。

• 无符号减法溢出判断条件：借位标志CF=C_outC_in=1
  做减法操作时（用同一个运算部件，减法转换成加法），C_in=1，所以CF=C_out1=C_out取反，所以对于无符号数减法，如果最高位没有产生进位，则表示溢出。这个不太好理解。可以转换成加法思考，两个无符号数相减，其实都是转换成加法，只是原来是直接相加，现在是加上减数的按位取反+1，只要加法结果溢出了，说明结果就是超过了可表示的范围，所以判断条件是一样的。如：35 - B = 0010 0011 + + 1 = 0010 0100 + B^'，B^'也视作一个无符号数，那么如果这个结果溢出（即CF=1），那么说明结果超出无符号数可表示范围。

• 带符号减法溢出判断条件：溢出标志OF=C_nC_n-1=1
  最高位的进位和次高位的进位不同时则产生溢出，或者说两个加数的符号位相同但与和符号位不同（用同一个运算部件，减法转换成加法），同加法分类讨论：
  a. 两个正数相减，或者两个负数相减，肯定不会溢出。（理由同带符号加法中一个正数和一个负数相加情况）
  b. 一个正数减一个负数，同两个正数相加，用OF=1判断；
  c. 一个负数减一个正数，同两个负数相加，用OF=1判断；

注：其实所谓的产生溢出，无非就是最后运算的结果超出了当前类型能表示的范围，所以同样两个数相加减，当成无符号数或有符号数，溢出结果就可能不同。另外虽然我们上面进行了分类讨论，但是对于输入到整数加减运算器中的两个数，计算机可不管你是无符号数还是带符号数，一律都按同样的方式进行运算，然后把标志位存下来，至于你要拿这个结果当无符号数还有符号数，或者判断是否借位/溢出，都是你的事，这一点要记在心里。

& 整数乘法运算中的溢出判断

两个n位整数相乘，结果只取2n位乘积中的低n位，高n位可以用来判断溢出：

• 无符号数：若高n位全0，则不溢出，否则溢出。这是因为对于无符号数，两数相乘结果不能超过低n位可表示范围，即高n位必须为0。如：25 = 5 x 5 = 0101 x 0101 = 0001 1001 = 1001 = 9 (= 25 - 16)。
• 带符号数：若高n位全0或全1，且等于低n位的最高位，（或者或高n+1位全0或全1），则不溢出，否则溢出。（这个结论怎么推理出来的，之后再补充）

需要注意计算机硬件是不判溢出的，仅保留2n位乘积，供软件使用，所以程序需进行一些防溢出的处理。

另外，整数乘法运算比较耗费时钟周期，因此编译器在处理变量与常数相乘时，往往用移位、加法和减法的组合来代替。如：x20 = x(16+4) = (x<<4)+(x<<2)，之前记得左移可能产生溢出，所以不论是否溢出，两种运算方式结果都是一样的。

& 整数除法运算中的截断处理

对于整数除法外，因为商的绝对值不可能比被除数的绝对值大，所以不会发生溢出，只有一种例外：带符号整数的-2^n-1/-1 = 2^n-1，记得我们介绍补码时曾说过补码能增加表示一个最小负数吗?不过它没有对应的正数，所以如果对它除-1，就发生溢出了。

另外，整数除法运算更耗时钟周期，所以为了缩短运算时间，编译器在处理一个变量与一个2的幂次形式的整数相除时，常用逻辑/算术右移运算来实现。如：3 = 12/4 = 0000 1100 >> 2 = 0000 0011 = 3，-3 = -12/4 = 1111 0100 >> 2 = 1111 1101 = -3。

整数除法是有可能不能整除的，那就必须采用朝零舍入的截断方式。

• 无符号数，带符号正整数：移出的低位直接丢弃。那就是说小数直接不要了，朝0舍入。如：3.5 = 14/4 = 0000 1110 >> 2 = 0000 0011 = 3。
• 带符号负整数：先加上偏移量 2^k-1，然后再右移k位，低位截断。为什么要这么做呢？我的理解是补码的小数直接不要了，其实是朝无穷大方向舍入（why？之后再补充），那么要移出k位，只要这k位不为0，我先加上k个1，那么肯定会向前进个位，因此最后的结果会再加1，变成朝零舍入。如：-3.5 = -14/4 = 1111 0010 >> 2 = 1111 1100 = -4，这个和带符号正整数出发得到的数值部分不一致。因此应该先加上偏移量2²-1 = 3，即(-14 + 2²-1)/4 = (1111 0010 + 0000 0011) >> 2 = 1111 1101 = -3。

& 浮点数运算

若两个规格化浮点数为A = M_a·2^E_a，B = M_b·2^E_b，则：
A±B = (M_a ± M_b·2^-(E_a-E_b))·2^E_a （假设E_a >= E_b）
A*B = (M_a * M_b)·2^(E_a+E_b)
A/B = (M_a / M_b)·2^(E_a-E_b)

以上运算有可能出现几种情况：
阶码上溢：正指数超过最大允许值（127） => +∞/-∞/溢出
阶码下溢：负指数超过最小允许值（-126） => +0/-0
尾数溢出：最高有效位有进位 => 右规 （结果不一定溢出）
非规格化尾数：数值部分高位为0 => 左规
右规或对阶时，右段有效位丢失 => 尾数舍入 （可以运算过程中添加保护位）

举例说明如何计算浮点数加/减法：
0.5 + (-0.4375)
= 1.000 x 2^-1 + (-1.110 x 2^-2) （规格化）
= 1.000 x 2^-1 + (-0.111 x 2^-1) （对阶，小阶向大阶看齐，尾数右移）
= 0.001 x 2^-1 （尾数加减）
= 1.000 x 2^-4 （规格化，左规：左移一位，阶码减1，判断是否有阶码溢出）
= 0.0625 （是否需要考虑舍入；如果尾数是0，则需将阶码也置0，表示0）

在尾数右移的过程中，可能会发生超出规定位数的情况，可以在尾数右边放一个保护位和一个舍入位，用来保护对阶时右移的位或中间结果，当左规时被移入尾数中，作为舍入判断的依据。
举个例子：（假设尾数只有3位有效位）
0.59375 = 0.5 + 0.09375 = 1.00 x 2^-1 + 1.10 x 2^-4 = 1.00 x 2^-1 + 0.00 x 2^-1 （没有附加位）= 1.00 x 2^-1 = 0.5
0.59375 = 0.5 + 0.09375 = 1.00 x 2^-1 + 1.10 x 2^-4 = 1.00 x 2^-1 + 0.0011 x 2^-1 （两位附加位）= 1.0011 x 2^-1 = 1.01 x 2^-1 （舍入进位） = 0.625 （结果比上面更精确）
IEEE 754舍入的方式主要有就近舍入（舍入为最近可表示的数），正向舍入（+∞方向），负向舍入（-∞方向），和朝0方向舍入（正数floor，负数ceil）

C语言中有float和double类型的浮点数，分别对应IEEE 754单精读浮点数格式和双精度浮点数格式，那么在类型强制转换的时候可能会有什么问题？（这就是为什么我们要学习数据在计算机中真正的存储形式）

• 从int转换为float时，不会发生溢出，但可能有数据被舍入（float尾数为23+1位）
  如：最大正数0111 ... 1111_32位 = 1.11 ... 1111_30位小数 x 2³⁰ = 1.11 ... 1111_23位小数 x 2³⁰（发生截断）
• 从float转换为int时，可能发生溢出，int没有小数，数据可能会向0方向被截断
• 从int转换为double时，能保留精确值（double尾数为52+1位）
• 从double转换为int时，可能发生溢出，int没有小数，数据可能会向0方向被截断
• 从float转换位double时，能保留精确值（double有效位数更多）
• 从double转换为float时，可能发生溢出，也可能有数据被舍入（有效尾数变少）

注：文中图片来源于mooc官网