整數溢位與未定義行為

發表於 分類於 閱讀次數： 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這道題來說，它的目的正是為了讓我們在“規則的鐐銬”下舞蹈，從而深刻理解整數表示、運算和編譯器行為。而我們在實際工程中，最安全、最清晰的寫法永遠是第一選擇。