《计算机是如何工作的人人都能懂的计算机软硬件工作原理》第 5 章 数字电路中的算术运算 阅读笔记 5第 5 章 数字电路中的算术运算在第 4 章中我们介绍了数字电路和逻辑门它们能让我们用硬件实现逻辑表达式。在本书的前面我们把计算机定义为可以通过编程来执行一组指令的电子设备。在本章中我将通过展示简单的逻辑门是如何为计算机执行的运算铺平道路把这些概念连接起来。我们将讨论所有计算机都会执行的一种运算——加法运算。首先我们复习二进制加法的基础知识。然后我们用逻辑门搭建加法运算硬件演示计算机中简单的门如何协同工作来执行有用的操作。最后我们将讨论计算机中有符号和无符号整数的表示。5.1 二进制加法让我们来看看二进制中加法的基础知识。加法的基本原理在所有的位值系统中都是一样的所以你已经有了一个良好的开端因为你已经知道如何在十进制中进行加法运算与其讨论抽象概念不如举个具体的例子将两个二进制 4 位数 0010 和 0011 相加如图 5-1 所示。图 5-1 两个二进制数相加图 5-2 两个二进制数的最低有效位相加现在向左移动一位再把这些值相加如图 5-3 所示。如图 5-3 所示这个位置需要计算 11这给我们带来一个有趣的转折。在十进制中我们用符号 2 表示 11但在二进制中我们只有两个符号0 和 1。在二进制中11 等于 10解释参见第 1 章​需要用两个位来表示但一个位置上只能有 1 位所以将 0 放在当前位置上将 1 进位到下一个位置如图 5-3 所示。现在我们可以移到下一个位置见图 5-4​当我们相加这些位时必须也把前一个位置的进位加进来由此得到 1001。图 5-3 2 的位置相加图 5-4 4 的位置相加图 5-5 8 的位置相加当所有位都加完后便得到了完整的二进制结果 0101。检查结果正确与否的一种方法是全部转换成十进制如图 5-6 所示。图 5-6 两个二进制数相加然后将各数及结果全部转换成十进制如图 5-6 所示二进制答案 (0101) 和预期的十进制答案 (5) 一致。很简单幸运的是不管基数是什么加法的运算方式都是一样的。基数之间唯一的不同是有多少符号可以使用。二进制使得加法特别简单因为每个位置上的加法运算总是恰好产生两个输出位每个位都只有两种可能的值输出1一为 0 或 1 的和数位 (S)表示加法运算结果的最低有效位。输出二为 0 或 1 的进位位 (Cout)。5.2 半加器假设我们想要构建一个数字电路把两个二进制数的某个位置加起来。开始时我们关注最低有效位。将两个数的最低有效位相加只需要两个二进制输入称为 A 和 B​其二进制输出是一个和数位 (S) 和一个进位位 (Cout)。我们把这样的电路称为半加器。图 5-7 展示了半加器符号。图 5-7 半加器符号图 5-8 半加器的运作如图 5-8 所示第一个数的最低有效位是输入 A第二个数的最低有效位是输入 B。和数是一个输出 S进位也是一个输出。半加器的内部可以实现为一个组合逻辑电路所以我们可以用真值表描述它如表 5-1 所示。注意A 和 B 是输入而 S 和 Cout 是输出。表 5-1 半加器真值表ABSC0000011010101101让我们来看看表 5-1 中的真值表。0 加 0 得 0无进位。0 加 1或 1 加 0得 1无进位。1 加 1 得 0进位为 1。现在怎样用数字逻辑门来实现它呢如果单看一个输出那么解决方案很简单如图 5-9 所示。只看图 5-9 的输出 S 的话可以发现它与 XOR 门的真值表参见第 4 章完全匹配。只看 Cout 的话可以发现它与 AND 门的输出匹配。因此仅用 XOR 和 AND 两个门就可以实现半加器如图 5-10 所示。图 5-9 半加器真值表的输出分别匹配 XOR 和 AND图 5-10 用 XOR 和 AND 两个逻辑门实现的半加器如图 5-10 所示数字输入 A 和 B 充当 XOR 门和 AND 门的输入。这两个门产生所需的输出 S 和 Cout。5.3 全加器半加器可以处理两个二进制数的最低有效位加法运算。但是每个后续位都需要一个额外的输入进位位 Cin。这是因为除了最低有效位之外每个位都需要处理一种情况即前一个位的加法运算产生了进位这个进位反过来又成为当前位的进位。增加 Cin 输入需要新的电路设计我们把这种电路称为全加器。如图 5-11 所示全加器的符号类似于半加器的符号不同之处仅在于多了一个额外的输入 Cin。图 5-12 给出了一个单个位二进制加法与全加器关系的例子。图 5-11 全加器符号图 5-12 全加器的运作全加器处理包含进位位的单个位加法。在图 5-12 所示的例子中我们进行 4 的位置上的加法运算。由于前一个位置上是 1 和 1因此产生进位 1。在当前位置全加器接收 3 个输入(A0B0Cin1)产生输出 S1 和 Cout0。为了全面了解全加器可能的输入和输出我们可以使用真值表如表 5-2 所示。这个表有 3 个输入 (A、B、Cin) 和 2 个输出 (S、Cout)。花点时间考虑一下各种输入组合对应的输出。怎样实现全加器呢顾名思义全加器可以通过两个半加器来实现见图 5-13​。表 5-2 全加器真值表ABCinSCout0000000110010100110110010101011100111111图 5-13 用两个半加器和一个 OR 门实现全加器全加器的和数位输出 (S) 应该是A 和 B 的和可以用一个半加器 HA1 计算再加上Cin可以用第二个半加器 HA2 计算​如图 5-13 所示。全加器还需要输出进位位。事实证明这实现起来很简单因为如果任何一个半加器的进位为1那么全加器中Cout的值就是1。因此我们可以用一个 OR 门来实现如图 5-13 所示。这也是封装的一个例子。电路构造好后就可以在不知道具体实现细节的情况下使用全加器功能了。下一节将介绍如何使用全加器和半加器来实现多位数的加法。5.4 4 位加法器全加器允许我们执行两个 1 位数再加上一个进位位的加法。这为我们提供了搭建电路的构建块使电路能进行多个位的二进制数加法。现在我们把几个 1 位加法器电路组合起来构成一个 4 位加法器。最低有效位用半加器因为它不需要进位位​其他位用全加器。如图 5-14 所示我们把加法器串在一起这样每个加法器的进位输出就会接入后续加法器的进位输入端。图 5-14 4 位加法器为了和人们书写数字的方式一致图 5-14 把最低有效位放在右边且计算流程是从右到左的。这就意味着我们的加法器框图的输入和输出位置将和前面展示的不同不要让它迷惑了你在图 5-15 中我用这个 4 位加法器重新计算了之前的例子00100011。图 5-15 4 位加法器的工作过程在图 5-15 中我们可以看到输入 A (0010) 和输入 B (0011) 是如何被送入每个加法器单元的从右边的最低有效位开始一直移动到左边的最高有效位。你可以按从右到左的顺序来处理图中的计算流程。首先将最右边的 0 (A0) 和 1 (B0) 相加结果为 1 (S0)进位为 0。最右边加法器的进位输出为 C1接入下一个加法器这个加法器会将 1 (A1) 和 1 (B1) 以及进位 0 相加。结果为 0 (S1) 和进位 1 (C2)。继续这个过程直到最左边的加法器完成运算为止。最终结果是一组输出位 0101 (S3S0) 和一个进位 0 (C4)。如果需要处理更多的位那么可以通过合并更多全加器来扩展图 5-15 中的设计。这种类型的加法器需要让进位位以波纹方式通过电路。因此我们称这个电路为行波进位加法器。每个进位位传递到下一个加法器都会引入一个小延迟所以扩展这种设计来处理更多位会让电路变慢。在全部进位位都传播到位之前电路的输出是不准确的。7400 系列 IC 提供了多个版本的 4 位加法器。如果你需要 4 位加法器那么可以使用这样的 IC不必用单个逻辑门来构建加法器。现在暂停一下考虑考虑刚才讨论的内容的更广泛的含义。你已经学习了如何构建 4 位加法器但这和计算有什么关系回想一下计算机是可以通过编程来执行一组逻辑指令的电子设备。这些指令包含了算术运算指令而且我们刚刚看到了如何把用晶体管构建的逻辑门组合起来执行其中一种运算加法运算。我们把加法作为计算机运算的一个具体例子进行了介绍尽管本书不做详细讨论但是你也可以用逻辑门实现其他基本的计算机运算。这就是计算机的工作方式——让简单的逻辑门协同工作来完成复杂的任务。5.5 有符号数到目前为止本章只关注了正整数但是如果我们也想处理负整数该怎么办呢我们需要考虑怎样在计算机这样的数字系统中表示负整数。计算机中的所有数据都被表示为 0 / 1 序列。负号既不是 0 也不是 1所以我们需要使用一种约定来表示数字系统中的负值。在计算机中有符号数 (signed number) 是一个位序列它可以用来表示负数或正数具体取决于这些位的值。设计数字系统时必须定义用多少位来表示一个整数。通常我们用 8 位、16 位、32 位或64 位来表示整数。这些位中的一个可以被分配用于表示负号。例如如果最高有效位为 0那么该数为正数如果最高有效位为 1那么该数为负数。其余的位则用来表示该数的绝对值。这种方式被称为原码表示。这是可行的但是为了考虑有特殊含义的位它会增加系统设计的复杂度。例如考虑到符号位我们之前构建的加法器电路就需要修改。在计算机中表示负数的更好方法被称为补码。在这种情况下一个数的补码表示的是这个数的负数。确定数的补码的最简单方式是把每个 1 用 0 代替把每个 0 用 1 代替即按位翻转​然后再加 1。这里请注意乍看之下这似乎过于复杂但如果你按照每一步进行便会发现很简单。让我们以 4 位数数字 5为例该数字用二进制表示为 0101。图 5-16 展示了确定该数补码的过程。图 5-16 确定 0101 的补码我们首先按位翻转然后再加 1得到二进制的 1011。因此在这个系统中5 表示为 0101-5 表示为1011。请记住1011 只是在 4 位有符号数的环境下才表示 -5。稍后我们会看到在不同的环境中这个二进制序列有不同的解释。反过来如果要确定负值的补码该怎么做呢过程是一样的如图 5-17 所示。图 5-17 确定 1011 的补码如同在图 5-17 中所看到的求取 -5 的补码便又得到了原来的值 5。这是有道理的因为 -5 的负数是 5。现在我们知道了如何用补码把一个数表示为正值或负值但这有什么用呢我认为了解这个系统好处的最简单的方法是尝试一下。假设我们想把 7 与 -3 相加即 7 减 3​。我们的期望结果为 4。我们先确定输入的二进制表示如图 5-18 所示。图 5-18 确定 7 和 -3 的 4 位补码我们的两个二进制输入是 0111 和 1101。现在暂时忘记我们处理的是正值和负值只把两个二进制数相加。不用担心各个位代表的是什么把它们相加就好然后准备迎接惊喜吧完成二进制运算后请看图 5-19。图 5-19 将两个二进制数的加法解释为有符号十进制数的加法如图 5-19 所示这个加法运算产生的进位超出了 4 位数能表示的范围。稍后将更详细地解释这一点但是现在我们先忽略这个进位位。因此便得到 4 位的结果 0100这就是我们期望的数字 4这就是补码表示法的美妙之处。在加法和减法运算过程中我们不需要任何特殊的处理它就能正常工作。我们在这里暂停一下先想想这件事的意义。还记得我们之前构建的那些加法器电路吗它们也适用于负值任何用于处理二进制加法的电路都可以使用补码作为处理负数或减法的手段。对所有这些工作原理的详细的数学解释超出了本书的范围如果你对此感兴趣网上有很好的解释。补码术语 “补码” 实际上是指两个相关的概念。补码是表示正整数和负整数的一种符号形式。例如数字 5 用 4 位补码表示为 0101而 -5 则表示为 1011。同时补码也是一种运算操作用于对以补码格式存储的整数取反。例如取 0101 的补码就得到 1011。还有一种看待补码的方法最高有效位的权重等于该位权重的负值其他所有位的权重等于相应位的权重。因此对于 4 位数而言每位的权重如图 5-20 所示。图 5-20 用补码表示的有符号4位数的位值权重如果我们把这种补码表示方法应用到 1101 (-3) 上我们就能计算出对应的十进制值如图 5-21 所示。图 5-21 使用补码的位值确定 1101 的有符号十进制值在处理补码时我发现把最高有效位的权重看作该位权重的负值是一种思维捷径。现在我们已经讨论了 4 位有符号数中所有位置的权重接下来我们可以检查用这样的数表示的全部值的范围如表 5-3 所示。二进制数有符号十进制数00000000110010200113010040101501106011171000-81001-71010-61011-51100-41101-31110-21111-1根据表 5-3我们可以观察到对于 4 位有符号数最大正值是 7最小负值是 -8一共有 16 个可能的值。请注意当最高有效位是 1 时数值为负。对于 n 位有符号数我们可以概括如下最大正值为 (2^n-1)-1最小负值为 -(2^n-1)数值的总数为 2^n。对于 8 位有符号数我们发现最大正值为 127最小负值为 -128数值总数为 256。5.6 无符号数有符号数用补码表示负值是处理负数的一种便捷方式它不需要专门的加法器硬件。之前我们介绍的加法器对负值和正值都有效。但是在计算机中有一些场景根本就不需要负值把数字当成有符号数只会浪费大约一半的取值范围所有的负值都不会用到​同时还把最大值限制为可以表示值的大约一半。因此在这种情况下我们希望把数字看作无符号的这意味着位序列总是表示正值或零而绝不会是负值。再看一下 4 位数当我们把它解释为有符号数或无符号数时表 5-4 给出了每个4位二进制值的含义。二进制有符号十进制无符号十进制0000000001110010220011330100440101550110660111771000-881001-791010-6101011-5111100-4121101-3131110-2141111-115对于 n 位无符号数我们概括如下最大值为 (2^n)-1最小值为 0数的总数为 2^n。我们举个 4 位数的例子如 1011。查查表 5-4这个值代表什么代表的是 -5 还是 11答案视情况而定它既可以代表-5也可以代表11这取决于上下文。从加法器电路的角度来看这无关紧要。对加法器来说它就只是 1011 而已。无论怎样加法运算都是按相同的方式来执行的唯一的区别是我们怎么解释其结果。让我们看个例子。在图 5-22 中我们把两个二进制数 1011 和 0010 相加。如图 5-22 所示无论使用的是有符号数还是无符号数这两个二进制数相加的结果都是 1101。在计算完成后我们要决定怎样解释结果。要么是 -5 加 2 得到 -3要么是 11 加 2 得到 13。任何一种情况下算术运算都是对的就是解读的问题而已在计算机环境中由在计算机上运行的程序负责正确解释加法运算的结果是有符号的还是无符号的。到目前为止我们基本上忽略了最高位的进位但我们应该理解它的含义。对于无符号数来说进位位为 1 意味着发生了整数溢出。换句话说就是结果太大无法用分配的表示整数的位数来表示。对于有符号数如果最高有效位的进位输入不等于其进位输出那么发生溢出。同样对于有符号数来说如果最高有效位的进位输入等于最高有效位的进位输出那么就没有发生溢出可以忽略进位位。整数溢出是计算机程序错误的来源。如果程序不检查是否发生溢出那么加法运算的结果可能会被错误解读从而导致意外行为。整数溢出错误的一个著名例子出现在街机游戏 Pac-Man 中。当玩家达到 256 级时屏幕右侧就全是混乱的图形。之所以出现这种情况是因为等级数是用 8 位无符号整数表示的其最大值 255 再加 1 就会导致溢出。游戏的逻辑没有考虑到这一点因而会出现故障。5.7 总结本章以加法运算为例来说明计算机是如何基于逻辑门来执行复杂任务的。你学习了如何执行二进制加法运算如何基于逻辑门构建硬件来执行二进制数的加法。你看到了半加器是怎样把两个位相加并产生一个和数位和一个进位位的明白了全加器可以实现两个位和一个进位位的加法运算。我们讨论了如何组合针对单个位的加法器以执行多个位的加法运算。你学到了如何在计算机中用有符号数和无符号数表示整数。