整数溢出与未定义行为

发表于 分类于 阅读次数： Waline： 本文字数： 3.4k

在做 CSAPP Data Lab 的时候，关于整数溢出，遇到一些问题。

题干

1
2
3
4
5
6
7
8
9
10
11
/*
 * isTmax - returns 1 if x is the maximum, two's complement number, 
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */

int isTmax(int x) {
  return 2;
}

题目要求，仅仅使用运算符 ! ~ & ^ | + 来判断一个数是否是最大的二的补码（int 范围内），即 0x7fffffff。如果是，输出 1；否则，输出 0。

思路

由于我们不能使用移位操作（很多人会直接 1<<31 - 1），可以考虑整数溢出的特殊性质。

具体地，我们有 0x7fffffff + 1 = 0x80000000，符号改变。

而 0x80000000 + 0x80000000 = 0

我们可以得到 x = 0x7fffffff 满足 x + 1 + x + 1 = 0

而对于其他数字，假设 y = x + k 其中 k 非零，则有 y + 1 + y + 1 = 2*k

此时，我们发现，对于 y=-1 也有 y + 1 + y + 1 = 0，需要排除掉

其他情况下，非零数转换为 bool 类型自动变为 1

我们不难写出以下代码：

1
2
3
4
5
int isTmax(int x) {
  int p1 = x+1;
  int p2 = p1 + p1;
  return !(p2) & !!(p1);
}

发现问题

这段代码在我本地（macOS，Apple clang version 17.0.0 (clang-1700.3.19.1), Target: arm64-apple-darwin25.0.0) 上运行，使用命令 clang main.c 是没有任何问题的。

但是，检查到 CSAPP 提供的 Makefile，有

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#
# Makefile that builds btest and other helper programs for the CS:APP data lab
# 
CC = gcc
CFLAGS = -O -Wall
LIBS = -lm

all: btest fshow ishow

btest: btest.c bits.c decl.c tests.c btest.h bits.h
	$(CC) $(CFLAGS) $(LIBS) -o btest bits.c btest.c decl.c tests.c

fshow: fshow.c
	$(CC) $(CFLAGS) -o fshow fshow.c

ishow: ishow.c
	$(CC) $(CFLAGS) -o ishow ishow.c

# Forces a recompile. Used by the driver program. 
btestexplicit:
	$(CC) $(CFLAGS) $(LIBS) -o btest bits.c btest.c decl.c tests.c 

clean:
	rm -f *.o btest fshow ishow *~

注意到，编译器使用了 -O flag，即 O1 优化。

此时执行这段代码，对于 0x7fffffff 输出 0，怀疑可能是编译器优化时，假设未定义行为（整数溢出）不会发生，将 !p2 优化。p1 + p1 的形式过于简单。

未定义行为

未定义行为（UB），根据 cppreference 的定义：

1
undefined behavior - There are no restrictions on the behavior of the program.

有符号整数溢出是一种常见的未定义行为。

Because correct C++ programs are free of undefined behavior, compilers may produce unexpected results when a program that actually has UB is compiled with optimization enabled.

也就是说，编译器优化会对未定义行为产生意料之外的结果

cppreference 给出了一个整数溢出的例子：

1
2
3
4
5
int foo(int x)
{
    return x + 1 > x; // either true or UB due to signed overflow
}

编译之后却变成了

1
2
3
foo(int):
        mov     eax, 1
        ret

意思是，不管怎么样都输出 1

观察出错代码

我们通过 gcc -S 输出编译后的汇编代码

1
2
3
4
5
6
7
_Z6isTmaxi:
.LFB2:
	.cfi_startproc
	endbr64
	movl	$0, %eax
	ret
	.cfi_endproc

我们看到，编译器直接把这个函数返回值改成了 0，不管输入什么，与我们的错误原因推断是相同的。

修改

我们可以尝试构造一个更复杂的、不易被简单规则匹配的表达式，躲过 O1 级别的优化。

核心思路不变，仍然是利用 Tmax + 1 = Tmin 这个特性。我们来观察一下 Tmax 和 Tmin 在二进制下的关系：

  • Tmax = 0x7fffffff = 0111...1111
  • Tmin = 0x80000000 = 1000...0000

一个非常有趣的性质是 Tmax + Tmin = -1 (0xffffffff)。

1
2
3
4
  0111 1111 ... 1111  (Tmax)
+ 1000 0000 ... 0000  (Tmin)
-------------------------
  1111 1111 ... 1111  (-1)

基于这个观察，我们可以设计一个新的检查方案：如果一个数 x 是 Tmax，那么 x + (x+1) 的结果就应该是 -1。取反后 ~(-1) 则为 0。

我们可以写出如下的修改版代码：

1
2
3
4
5
int isTmax(int x) {
  int map = x + 1;
  int res = ~(map + x);
  return !res & (!!map);
}

这段代码的逻辑是：

  1. 计算 map = x + 1。对于 x = Tmax，这里同样会发生有符号溢出，map 变为 Tmin。这依然是未定义行为（UB）。
  2. 计算 res = ~(map + x)。如果 x 是 Tmax，这一步就是 ~(Tmin + Tmax)，结果为 ~(-1)，即 0。
  3. return !res & (!!map)。!res 为 !0，即 1。!!map 部分和之前的版本一样，是为了排除 x = -1 的情况（此时 map 为 0， !!map 为 0，最终返回 0）。

这段代码在 -O 优化下可能会得到正确的结果。

为什么这个“可能”有效？

我们必须清醒地认识到，新版本的代码本质上没有解决未定义行为的问题，它只是“侥幸”地绕过了当前编译器版本的特定优化策略。

  • 代码模式的复杂性：p1 + p1 ((x+1)+(x+1)) 是一个非常简单直白的模式，优化器很容易建立一个“如果 p1 非零，则 p1+p1 结果也非零”的优化规则。而 ~((x+1)+x) 混合了加法和位运算，模式更复杂，可能没有触发编译器中已有的、基于UB的优化捷径。
  • 优化的机会主义：编译器优化并不是要穷尽所有的数学可能，而是应用一系列已知的高效模式。我们的新代码恰好不在这些常见模式的“黑名单”上。

所以，这个修改版只是一个更具迷惑性的“伪装”。它在特定环境下能工作，但其行为是不被C语言标准所保证的，在不同的编译器或未来的GCC版本下，它随时可能失效。

结论：如何正确面对未定义行为

通过 isTmax 这个小小的函数，我们可以一窥C语言中未定义行为的危险性以及现代编译器优化的强大。作为开发者，我们应该得到以下启示：

  1. 不要依赖未定义行为：永远不要编写依赖于UB的代码，即使它“在你的机器上看起来能跑”。代码的健壮性来源于对语言标准的严格遵守，而非侥幸。
  2. 相信编译器，但要验证：编译器非常聪明，它会严格按照语言规范进行优化。当你发现优化后的代码行为不符合你的“直觉”时，首先应该怀疑自己的代码是否触碰了UB的红线。
  3. 善用工具：
    • 始终开启编译器警告 (-Wall -Wextra) 并将警告视为错误 (-Werror)，这能帮你发现许多潜在问题。
    • 使用运行时检测工具，如GCC/Clang的 UndefinedBehaviorSanitizer (UBSan)。只需在编译时加上 -fsanitize=undefined，它就能在程序运行时精确地捕获有符号整数溢出等UB，是调试这类问题的神器。

对于CSAPP Data Lab这道题来说，它的目的正是为了让我们在“规则的镣铐”下舞蹈，从而深刻理解整数表示、运算和编译器行为。而我们在实际工程中，最安全、最清晰的写法永远是第一选择。