信息的处理和表示

习题

2.31 双重溢出

1
2
3
4
5
6
/* 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); 
}

核心原因：无论 x + y 是否溢出，表达式 (sum - x == y) 和 (sum - y == x) 在补码运算中永远恒为真（1）。

该函数对于任何输入都会返回 1，完全起不到检测溢出的作用。

原理解析：模算术下的阿贝尔群

补码的加法和减法在机器字长为 $w$ 位（如 32 位）的底层硬件中，本质上都是在模 $2^w$ 的整数环（数学上的阿贝尔群）中进行的。

  1. 加法运算：
    $$\text{sum} = (x + y) \bmod 2^w$$

  2. 紧接着的减法运算：
    由于模运算满足结合律与逆元性质：
    $$\text{sum} - x \equiv ((x + y) - x) \pmod{2^w} \equiv y \pmod{2^w}$$

加法溢出所产生的位回绕，会被后续减法溢出所产生的位回绕完全抵消。

具象数值推导（以 4 位补码为例）

在 4 位补码系统中：

  • 表示范围：$[-8, 7]$
  • 模数：$2^4 = 16$

设：$x = 5$，$y = 4$（真实和为 $9 > 7$，发生正溢出）。

  1. 计算 sum：
    $$5 + 4 = 9 \xrightarrow{\text{模 16 截断}} 9 - 16 = -7$$
    内存中 sum 的实际值为 $-7$。

  2. 计算 sum - x：
    $$\text{sum} - x = -7 - 5 = -12$$
    $-12$ 超出下界，发生负溢出并做模 16 回绕：
    $$-12 + 16 = 4$$
    计算结果为 $4$。

  3. 执行判断：
    计算得到的 sum - x 为 $4$，而参数 y 的值也是 $4$：
    $$(4 == 4) \implies \text{True}$$

即使发生了严重溢出，(sum - x == y) 依然判定为真。

正确的实现方式

不能通过事后减法来反推，而应该通过操作数与结果的符号位变化来判定：

1
2
3
4
5
6
7
8
/* 正确检测补码加法溢出的实现 */
int tadd_ok(int x, int y) {
    int sum = x + y;
    int neg_over = (x < 0) && (y < 0) && (sum >= 0); // 两个负数相加，结果 >= 0（负溢出）
    int pos_over = (x > 0) && (y > 0) && (sum < 0);  // 两个正数相加，结果 < 0（正溢出）

    return !neg_over && !pos_over; // 无溢出返回 1，溢出返回 0
}