第二十四课:固定位宽为什么会溢出

从 7 加 1 出发,判断有符号溢出,并区分它与最终进位。

本章目录CONTENTS ↓

上一课把减法改写成了加法。现在需要检查另一个问题:加法器给出一串固定宽度的比特,我们能否始终把它当作正确的数学答案?先用 4 位计算 7 + 1:

0111 7
+ 0001 1
-------
1000 按 4 位补码解释为 −8

逐位相加得到 1000,电路没有算错。但如果把输出按 4 位补码解释,1000 表示 −8,而数学答案是 +8。差别从哪里来?

电路算出了位串,位串装不下答案

第二十二课已经推导过:4 位补码只能表示 −8 到 7。输入 7 和 1 都在范围内,精确的和 8 却超出了范围。加法器照常输出低 4 位 1000,但这串比特无法表示数学答案 +8。这叫有符号溢出(signed overflow)。改用 5 位时,00111 + 00001 = 01000 可以表示 +8;只是 5 位也有自己的边界。补码的范围

上一课留下的 −8 取相反数问题,原因也一样:−8 是 4 位补码的最小值,数学上的相反数 +8 不在范围内。对 1000 逐位取反得到 0111,再加 1 又得到 1000。运算步骤仍按规则执行,只是结果不能表示期望的 +8。这是同一个边界问题,不需要另记一套规则。

最终进位回答的是另一个问题

从最高位向外传出的比特叫最终进位(final carry-out)。在 4 位加法中,它告诉我们:如果把两串输入当作无符号数,完整的和是否超过 15。有符号溢出问的却是:如果把输入当作补码数,数学结果是否超出 −8 到 7。比较这两组输入:

位串相加 按无符号数计算 最终进位 按补码计算 有符号溢出?
0111 + 0001 = 1000 7 + 1 = 8 0 7 + 1 = 8,超出范围 是
0101 + 1011 = 1 0000 5 + 11 = 16 1 5 + (−5) = 0,在范围内 否

第一组没有最终进位,却发生了有符号溢出;第二组有最终进位,低 4 位 0000 却正确表示数学答案 0。只看最终进位,无法判断有符号溢出。这是因为两种判断采用了不同的数值解释和范围。

回到课程中的 16 位加法器

16 位补码能表示 −32768 到 32767,因此 32767 + 1 也会越界。Add16 输出 1000 0000 0000 0000;按 16 位补码读,它是 −32768,不是数学答案 +32768。Hack ALU 同样只给出固定宽度的运算结果。官方规格明确说明,Add16 与 ALU 都不检测或处理溢出。官方 Chapter 2:加法器与 ALU 规格

如果应用需要准确的整数结果,就要另外检查是否溢出,或使用足够宽的表示。在线模拟 Add16 时,可以试一试 0111 1111 1111 1111 + 0000 0000 0000 0001:先预测输出位串,再分别说出它和数学答案代表什么。

这节课的判断顺序是:先看输入采用什么表示规则和位宽,再看精确的数学结果是否落在可表示范围内。电路正确输出位串,不保证该位串按补码解释后仍是期望的答案。有疑问可以先问我;学完后,我们再按一次一题的节奏练习。

参考资料:官方 Project 2、官方 Chapter 2。资料供自愿查阅,不作为额外阅读任务。

这一页,先记到这里。