CSAPP 習題 2.10 詳解：inplace_swap 異或交換的逐步推導與驗證

CSAPP 習題 2.10 詳解：inplace_swap 異或交換的逐步推導與驗證

CSAPP 2.10 要求分析無臨時變量的異或交換算法。本文通過真值表逐步推導三條語句如何將 *x、*y 從 a、b 變為 b、a，並說明其數學原理。

算法代碼

void inplace_swap(int *x, int *y) {
    *y = *x ^ *y;  // 步驟 1
    *x = *x ^ *y;  // 步驟 2
    *y = *x ^ *y;  // 步驟 3
}

逐步狀態推導表

核心數學性質

• 交換律：a ^ b == b ^ a
• 結合律：(a ^ b) ^ c == a ^ (b ^ c)
• 自反性：a ^ a == 0
• 單位元：a ^ 0 == a

正是這四條性質，保證了三步異或操作能在不引入臨時變量的情況下完成交換。

⚠️ 關鍵前提：x 與 y 必須指向不同地址

若 x == y（別名），步驟 1 即將該地址值置 0，後續全為 0。這正是 CSAPP 2.11 奇數長度數組反轉失敗的根因。

現代編譯器視角

GCC/Clang/MSVC 在優化等級 -O2 以上時，會將「臨時變量交換」優化為寄存器 XCHG 指令或等效移動序列，性能不劣於異或交換，且無別名風險、可讀性高。因此：

工程實踐建議：優先寫 tmp = *x; *x = *y; *y = tmp;，讓編譯器做優化。

總結

異或交換是位運算經典教學案例，展示了布爾代數在計算機系統中的巧妙應用。理解其推導過程有助於深入掌握位級操作，但實際項目中請使用臨時變量版本。