文章目录
- 线索栏
- 笔记栏
-
- 1. 补码加法的目标与范围
- 2. 补码加法公式（等式2.13）
- 3. 公式推导与四种情况（结合图2-24和图2-26）
- 4. 溢出检测原理
- 5. 4位补码加法示例（图2-25）
- 6.练习题
-
- 练习题2.29
- 练习题2.30
- 练习题2.31
- 练习题2.32
- 总结栏
线索栏
笔记栏
1. 补码加法的目标与范围
（1）目标：给定两个 w位的补码整数 x和 y（范围
−
2
w
−
1
≤
x
,
y
≤
2
w
−
1
−
1
−2^{w−1}≤x,y≤2^{w−1}−1
−2w−1≤x,y≤2w−1−1），计算它们的和 x+y，并用 w位补码表示。 （2）真实和的范围：x+y的数学值在
−
2
w
≤
x
+
y
≤
2
w
−
2
−2^w≤x+y≤2^w−2
−2w≤x+y≤2w−2之间，可能需要 w+1位来表示。 （3）处理方法：将真实和截断到 w位，并将结果解释为补码数。定义运算
+
w
t
+_w^t
+wt表示此过程：
x
+
w
t
y
=
T
r
u
n
c
a
t
e
(
x
+
y
)
x+_w^ty=Truncate(x+y)
x+wty=Truncate(x+y)。
2. 补码加法公式（等式2.13）
对于满足范围
−
2
w
−
1
≤
x
,
y
≤
2
w
−
1
−
1
−2^{w−1}≤x,y≤2^{w−1}−1
−2w−1≤x,y≤2w−1−1的整数 x和 y，它们的 w位补码和定义为：
x
+
w
t
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
(负溢出)
x +_{w}^{t} y = \\begin{cases} x + y – 2^{w}, & 2^{w-1} \\leq x + y \\quad \\text{(正溢出)} \\\\[0.5em] x + y, & -2^{w-1} \\leq x + y < 2^{w-1} \\quad \\text{(正常)} \\\\[0.5em] x + y + 2^{w}, & x + y < -2^{w-1} \\quad \\text{(负溢出)} \\end{cases}
x+wty=⎩
⎨
⎧x+y−2w,x+y,x+y+2w,2w−1≤x+y(正溢出)−2w−1≤x+y<2w−1(正常)x+y<−2w−1(负溢出)
3. 公式推导与四种情况（结合图2-24和图2-26）
设
z
=
x
+
y
z=x+y
z=x+y（真实整数和），
z
′
=
z
m
o
d
2
w
z′=zmod2^w
z′=zmod2w（模结果），
z
′′
=
U
2
T
w
(
z
′
)
z′′=U2T_w (z′)
z′′=U2Tw(z′)（最终补码解释）。 （1）情况1（负溢出）：
x
+
y
<
−
2
w
−
1
x+y<−2^{w−1}
x+y<−2w−1。则
z
′
=
z
+
2
w
z′ =z+2^w
z′=z+2w，且
z
′′
=
z
′
=
z
+
2
w
z′′=z′=z+2^w
z′′=z′=z+2w。结果比真实和大
2
w
2^w
2w。 （2）情况2（正常，负）：
−
2
w
−
1
≤
x
+
y
<
0
−2^{w−1}≤x+y<0
−2w−1≤x+y<0。则
z
′
=
z
+
2
w
z′=z+2^w
z′=z+2w，但
z
′′
=
z
′
−
2
w
=
z
z′′=z′−2^w=z
z′′=z′−2w=z。结果正确。 （3）情况3（正常，正）：
0
≤
x
+
y
<
2
w
−
1
0≤x+y<2^{w−1}
0≤x+y<2w−1。则
z
′
=
z
，
z
′′
=
z
z′=z，z′′=z
z′=z，z′′=z。结果正确。 （4）情况4（正溢出）：
2
w
−
1
≤
x
+
y
2^{w−1}≤x+y
2w−1≤x+y。则
z
′
=
z
z′=z
z′=z，但
z
′′
=
z
′
−
2
w
=
z
−
2
w
z′′=z′−2^w=z−2^w
z′′=z′−2w=z−2w。结果比真实和小
2
w
2^w
2w。
4. 溢出检测原理
对于满足
T
M
i
n
w
≤
x
,
y
≤
T
M
a
x
w
TMin_w≤x,y≤TMax_w
TMinw≤x,y≤TMaxw的 x和 y，令
s
=
x
+
w
t
y
s=x+_w^ty
s=x+wty。 （1）正溢出：当且仅当
x
>
0
，
y
>
0
x>0，y>0
x>0，y>0，但
s
≤
0
s≤0
s≤0时发生。 （2）负溢出：当且仅当
x
<
0
，
y
<
0
x<0，y<0
x<0，y<0，但
s
≥
0
s≥0
s≥0时发生。
5. 4位补码加法示例（图2-25）
可以通过对操作数进行二进制加法并截断到 w位来获得补码和的位级表示。溢出的特征是：同号相加，结果符号与加数相反。
6.练习题
练习题2.29
计算过程简述（以第一行为例）： x=[10100]解释为5位补码：最高位1表示负数，数值部分 0100=4，因此值 = -16+4 = -12（注：这里应为-12，但整数和计算是x+y，x和y的值：x=-12, y=-15？仔细计算：[10100]是 -12，[10001]是 -15，整数和 = -12-15 = -27，正确。补码和：二进制加法 10100+10001=100101，截断5位得 00101，解释为补码是 5。由于整数和 -27 < TMin_5=-16，属于负溢出，结果 = -27+2^5 = 5，匹配。） 
练习题2.30
int tadd_ok(int x, int y) {
int sum = x + y;
// 正溢出：两个正数相加得负数或零；负溢出：两个负数相加得正数或零
int pos_over = (x > 0) && (y > 0) && (sum <= 0);
int neg_over = (x < 0) && (y < 0) && (sum >= 0);
return !pos_over && !neg_over; // 无溢出时返回1
}
练习题2.31
有bug的代码：
/* 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
有bug的代码：
/* 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);
}
正确代码：
#include <limits.h> // 使用 INT_MIN
// 假设 tadd_ok 已正确定义
int tadd_ok(int x, int y);
int tsub_ok(int x, int y) {
// 处理 y 为 TMin 的特殊情况
if (y == INT_MIN) {
// 仅当 x < 0 时，x – TMin 不会溢出（结果范围 0 ~ TMax）
return x < 0;
}
// 其他情况，转化为加法检测
return tadd_ok(x, –y);
}
总结栏
本节定义了
w
w
w位补码加法
+
w
t
+_w^t
+wt ，其核心是通过截断处理有限精度下的溢出问题。
[
−
2
w
−
1
,
2
w
−
1
−
1
]
[−2^{w−1},2^{w−1}−1]
[−2w−1,2w−1−1]范围内，结果准确。 （2）正溢出：两个正数相加，和
≥
2
w
−
1
≥2^{w−1}
≥2w−1，结果变为负数（
s
=
x
+
y
−
2
w
s=x+y−2^w
s=x+y−2w）。 （3）负溢出：两个负数相加，和
<
−
2
w
−
1
<−2^{w−1}
<−2w−1，结果变为正数（
s
=
x
+
y
+
2
w
s=x+y+2^w
s=x+y+2w）。
w
=
4
，
2
w
=
16
w=4，2^w=16
w=4，2w=16。负溢出时和增加16，正溢出时和减少16（见图2-26的“斜面”图示）。
核心启示：理解补码加法的截断行为（特别是溢出时的“回绕”方向），并掌握其简洁的检测条件（同号相加结果异号），对于编写正确且可靠的整数运算代码至关重要，尤其是在涉及可能很大的正数或负数的累加时。
