2.3.2 补码加法

对于补码加法，我们必须确定当结果太大（为正）或者太小（为负）时，应该做些什么。给定在范围 -2^w-1 ≤ x, y ≤ 2^w-1 - 1 之内的整数值 x 和 y，它们的和就在范围 -2^w ≤ x + y ≤ 2^w - 2 之内，要想准确表示，可能需要 w + 1 位。就像以前一样，我们通过将表示截断到 w 位，来避免数据大小的不断扩张。然而，结果却不像模数加法那样在数学上感觉很熟悉。定义 x +^t_w y 为整数和 x + y 被截断为 w 位的结果，并将这个结果看做是补码数。

原理：补码加法

对满足 -2^w-1 ≤ x, y ≤ 2^w-1 - 1 的整数 x 和 y，有：

x +^t_w y	条件	情况
x + y - 2^w	2^w-1 ≤ x + y	正溢出
x + y	-2^w-1 ≤ x + y < 2^w-1	正常
x + y + 2^w	x + y < -2^w-1	负溢出

（2.13）

图 2-24 说明了这个原理，其中，左边的和 x + y 的取值范围为 -2^w ≤ x + y ≤ 2^w - 2，右边显示的是该和数截断为 w 位补码的结果。（图中的标号“情况 1”到“情况 4”用于该原理形式化推导的案例分析中。）当和 x + y 超过 TMax_w 时（情况 4），我们说发生了正溢出。在这种情况下，截断的结果是从和数中减去 2^w。当和 x + y 小于 TMin_w 时（情况 1），我们说发生了负溢出。在这种情况下，截断的结果是把和数加上 2^w。

两个数的 w 位补码之和与无符号之和有完全相同的位级表示。实际上，大多数计算机使用同样的机器指令来执行无符号或者有符号加法。

图 2-24 整数和补码加法之间的关系

推导：补码加法

既然补码加法与无符号数加法有相同的位级表示，我们就可以按如下步骤表示运算 +^t_w：将其参数转换为无符号数，执行无符号数加法，再将结果转换为补码：

x +^t_w y ≐ U2T_w(T2U_w(x) +^u_w T2U_w(y))　（2.14）

根据等式 (2.6)，我们可以把 T2U_w(x) 写成 x_w-12^w + x，把 T2U_w(y) 写成 y_w-12^w + y。使用属性，即 +^u_w 是模 2^w 的加法，以及模数加法的属性，我们就能得到：

x +^t_w y = U2T_w(T2U_w(x) +^u_w T2U_w(y))

= U2T_w[(x_w-12^w + x + y_w-12^w + y) mod 2^w]

= U2T_w[(x + y) mod 2^w]

消除了 x_w-12^w 和 y_w-12^w 这两项，因为它们模 2^w 等于 0。

为了更好地理解这个数量，定义 z 为整数和 z = x + y，z' 为 z' = z mod 2^w，而 z'' 为 z'' = U2T_w(z')。数值 z'' 等于 x +^t_w y。我们分成 4 种情况分析，如图 2-24 所示。

-2^w ≤ z < -2^w-1。然后，我们会有 z' = z + 2^w。这就得出 0 ≤ z' < -2^w-1 + 2^w = 2^w-1。检查等式 (2.7)，我们看到 z' 在满足 z'' = z' 的范围之内。这种情况称为负溢出（negative overflow）。我们将两个负数 x 和 y 相加（这是我们能得到 z < -2^w-1 的唯一方式），得到一个非负的结果 z'' = x + y + 2^w。
-2^w-1 ≤ z < 0。那么，我们又将有 z' = z + 2^w，得到 -2^w-1 + 2^w = 2^w-1 ≤ z' < 2^w。检查等式 (2.7)，我们看到 z' 在满足 z'' = z' - 2^w 的范围之内，因此 z'' = z' - 2^w = z + 2^w - 2^w = z。也就是说，我们的补码和 z'' 等于整数和 x + y。
0 ≤ z < 2^w-1。那么，我们将有 z' = z，得到 0 ≤ z' < 2^w-1，因此 z'' = z' = z。补码和 z'' 又等于整数和 x + y。
2^w-1 ≤ z < 2^w。我们又将有 z' = z，得到 2^w-1 ≤ z' < 2^w。但是在这个范围内，我们有 z'' = z' - 2^w，得到 z'' = x + y - 2^w。这种情况称为正溢出（positive overflow）。我们将正数 x 和 y 相加（这是我们能得到 z ≥ 2^w-1 的唯一方式），得到一个负数结果 z'' = x + y - 2^w。■

图 2-25 展示了一些 4 位补码加法的示例作为说明。每个示例的情况都被标号为对应于等式 (2.13) 的推导过程中的情况。注意 2⁴ = 16，因此负溢出得到的结果比整数和大 16，而正溢出得到的结果比之小 16。我们包括了运算数和结果的位级表示。可以观察到，能够通过对运算数执行二进制加法并将结果截断到 4 位，从而得到结果。

x	y	x + y	x +^t₄ y	情况
-8 [1000]	-5 [1011]	-13 [10011]	3 [0011]	1
-8 [1000]	-8 [1000]	-16 [10000]	0 [0000]	1
-8 [1000]	5 [0101]	-3 [11101]	-3 [1101]	2
2 [0010]	5 [0101]	7 [00111]	7 [0111]	3
5 [0101]	5 [0101]	10 [01010]	-6 [1010]	4

图 2-25　补码加法示例。通过执行运算数的二进制加法并将结果截断到 4 位，可以获得 4 位补码和的位级表示

图 2-26 阐述了字长 w = 4 的补码加法。运算数的范围为 -8~7 之间。当 x + y < -8 时，补码加法就会负溢出，导致和增加了 16。当 -8 ≤ x + y < 8 时，加法就产生 x + y。当 x + y ≥ 8 时，加法就会正溢出，使得和减少了 16。这三种情况中的每一种都形成了图中的一个斜面。

图 2-26 补码加法

等式 (2.13) 也让我们认出了哪些情况下会发生溢出：

原理：检测补码加法中的溢出

对满足 TMin_w ≤ x, y ≤ TMax_w 的 x 和 y，令 s = x +^t_w y。当且仅当 x > 0，y > 0，但 s ≤ 0 时，计算 s 发生了正溢出。当且仅当 x < 0，y < 0，但 s ≥ 0 时，计算 s 发生了负溢出。

图 2-25 显示了当 w = 4 时，这个原理的例子。第一个条目是负溢出的情况，两个负数相加得到一个正数。最后一个条目是正溢出的情况，两个正数相加得到一个负数。

推导：检测补码加法中的溢出

让我们先来分析正溢出。如果 x > 0，y > 0，而 s ≤ 0，那么显然发生了正溢出。反过来，正溢出的条件为：1）x > 0，y > 0（或者 x + y > TMax_w），2）s ≤ 0（见公式 (2.13)）。同样的讨论也适用于负溢出情况。■

练习题 2.29

按照图 2-25 的形式填写下表。分别列出 5 位参数的整数值、整数和与补码和的数值、补码和的位级表示，以及属于等式 (2.13) 推导中的哪种情况。

x	y	x + y	x +^t₅ y	情况
[10100]	[10001]
[11000]	[11000]
[10111]	[01000]
[00010]	[00101]
[01100]	[00100]

练习题 2.30

写出一个具有如下原型的函数：

/* Determine whether arguments can be added without overflow */
int tadd_ok(int x, int y);

如果参数 x 和 y 相加不会产生溢出，这个函数就返回 1。

练习题 2.31

你的同事对你补码加法溢出条件的分析有些不耐烦了，他给出了一个函数 tadd_ok 的实现，如下所示：

/* Determine whether arguments can be added without overflow */
/* WARNING: This code is buggy. */
int tadd_ok(int x, int y) {
    int sum = x+y;
    return (sum-x == y) && (sum-y == x);
}

你看了代码以后笑了。解释一下为什么。

练习题 2.32

你现在有个任务，编写函数 tsub_ok 的代码，函数的参数是 x 和 y，如果计算 x - y 不产生溢出，函数就返回 1。假设你写的练习题 2.30 的代码如下所示：

/* Determine whether arguments can be subtracted without overflow */
/* WARNING: This code is buggy. */
int tsub_ok(int x, int y) {
    return tadd_ok(x, -y);
}

x 和 y 取什么值时，这个函数会产生错误的结果？写一个该函数的正确版本（家庭作业 2.74）。