首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> 關於C語言

無臨時變量交換兩整數:加減法與異或交換法的原理、邊界與工程選擇

     編輯:關於C語言

問題引入

經典面試題:不使用第三個變量,交換兩個整型變量 a、b 的值。

給定極值測試:int a = INT_MAX (2³¹-1); int b = INT_MIN (-2³¹);

方法一:加減法(僅適用於無溢出場景)

a = a + b;
b = a - b; // 原 a
a = a - b; // 原 b

原理:利用加法可逆性。a+b 保存和,減去其中一個得另一個。

致命缺陷:有符號整數溢出屬於未定義行為(UB)。測試極值時 a+b 會溢出(INT_MAX + INT_MIN = -1 但標準不保證),導致程式崩潰或產生錯誤結果。**不可用於通用交換**。

方法二:異或交換法(通用、無溢出風險)

a = a ^ b;
b = a ^ b; // = (a^b)^b = a
a = a ^ b; // = (a^b)^a = b

原理:異或運算滿足 自逆性:x ^ y ^ y = x、x ^ x = 0、x ^ 0 = x。位運算**不產生進位/借位**,**絕不溢出**,對所有整數位模式(包括負數、補碼表示)均安全。

深度對比

維度加減法異或法
溢出安全性❌ 有符號 UB✅ 完全安全
適用類型無符號/浮點(有精度損失)所有整數類型
同地址別名❌ 歸零❌ 歸零
現代 CPU 效能加減指令延遲低XOR 指令同級,極快
可讀性直觀需位運算知識

關鍵陷阱:別名問題

若 &a == &b(同一記憶體位置),兩種方法**都會將值清零**:

a ^= a; // 0
// 後續操作全在 0 上進行,結果均為 0

工程強制要求:交換函數**必須檢查指針是否相等**。

工程級最佳實踐

// 通用、安全、編譯器可優化為單指令(xchg/mov)
static inline void swap_int(int *a, int *b) {
    if (a == b) return; // 關鍵:別名檢查
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// C11 泛型宏(支援任意類型)
#define SWAP(type, a, b) do { type tmp = (a); (a) = (b); (b) = tmp; } while(0)

// C++ 標準庫(最優選)
#include <utility>
std::swap(a, b); // 移動語義優化,處理別名,型別安全

為什麼現代編譯器不推薦「無臨時變量」技巧?

  1. 臨時變量極廉價:寄存器分配器會將 tmp 置於寄存器,**零記憶體開銷**。
  2. 別名分析友好:tmp 明確切斷依賴鏈,利於指令級並行(ILP)與向量化。
  3. 異或法阻礙優化:數據流分析難以識別「交換」語義,可能生成多餘指令。
  4. 可維護性:std::swap 一目瞭然,異或法需註釋解釋。

總結

異或交換法在理論上優雅且無溢出風險,是理解位運算自逆性的絕佳教材。但**工程實踐中,請毫不猶豫地使用臨時變量或 std::swap**。面試時可展示異或法並說明原理,隨即補充:「實際代碼中我會用 std::swap,因為更安全、更快、更易讀。」這才是資深工程師的回答。

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved