CSAPP 習題 2.11 詳解：reverse_array 中間元素歸零的根因與修復

CSAPP 習題 2.11 詳解：reverse_array 中間元素歸零的根因與修復

《深入理解計算機系統》(CSAPP) 2.11 題揭示了一個經典的原地交換陷阱：當數組長度為奇數時，中間元素會被錯誤置零。本文逐步拆解原因並給出最小修復方案。

問題代碼

void inplace_swap(int *x, int *y) {
    *y = *x ^ *y;
    *x = *x ^ *y;
    *y = *x ^ *y;
}

void reverse_array(int a[], int cnt) {
    int first, last;
    for (first = 0, last = cnt - 1; first <= last; first++, last--) {
        inplace_swap(&a[first], &a[last]);
    }
}

現象觀察

根因分析

當 cnt = 2k+1 時，循環最後一次滿足 first == last == k，即同一地址自我交換：

// 假設 a[k] = p
*y = *x ^ *y;  // *y = p ^ p = 0
*x = *x ^ *y;  // *x = p ^ 0 = p
*y = *x ^ *y;  // *y = p ^ 0 = p  ❌ 但此時 *x 和 *y 是同一地址！
// 實際執行流：
// 步驟1: a[k] = p ^ p = 0
// 步驟2: a[k] = 0 ^ 0 = 0
// 步驟3: a[k] = 0 ^ 0 = 0
// 結論：彈性交換算法要求 x != y，否則全歸零

修復方案：修改循環終止條件

// 只需將 <= 改為 <
for (first = 0, last = cnt - 1; first < last; first++, last--) {
    inplace_swap(&a[first], &a[last]);
}

理由：奇數長度時，中間元素無需交換（自己跟自己換無意義）；偶數長度時，first < last 恰好覆蓋所有成對元素。

驗證修復後結果

輸入: {1,2,3,4,5}
輸出: {5,4,3,2,1}  ✅ 中間元素 3 保持不變

延伸思考：何時可以用 XOR 交換？

• ✅ 兩個不同地址的整型變量
• ❌ 同一地址（別名）
• ❌ 浮點數（IEEE 754 位模式交換語義不同）
• ❌ 可能被編譯器優化掉的臨時變量

現代建議：除嵌入式極度受限環境外，優先使用臨時變量交換（tmp = *x; *x = *y; *y = tmp;），可讀性強、無別名風險、編譯器易優化為寄存器交換指令。

總結

CSAPP 2.11 用一個微小的邊界條件（奇數長度）暴露了 XOR 交換的別名問題。修復只需一字符（<= → <），卻體現了「循環不變式精確定義」的工程嚴謹性。