巧用異或 (XOR) 運算：從交換變數到高效查找算法

編輯：關於C語言

異或 (XOR, ^) 是位元運算中的「魔術師」：a ^ a = 0、a ^ 0 = a、滿足交換律與結合律。善用這三大特性，能寫出極精簡、無暫存變數、甚至無分支的高效代碼。本文展示三大經典應用場景。

1. 無暫存變數交換兩整數

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

無需 temp，但注意 a 與 b 必須為不同記憶體位址，否則會歸零。

2. 陣列中找出唯一落單元素 (其餘皆成對)

int findSingle(int *arr, int n) {
    int res = 0;
    for (int i = 0; i < n; i++) res ^= arr[i];
    return res;  // 成對者抵消為 0，落單者保留
}

時間 O(n)，空間 O(1)，極致優雅。

3. 原文高階應用：有序陣列中判斷是否存在兩數和為 X

利用 XOR 將「大小比較」與「遞增/遞減方向」融合為單一條件，消除分支：

// 遞迴版
bool judge_rec(int *a, size_t n, int x) {
    if (n < 2) return false;
    if (x == a[0] + a[n-1]) return true;
    // (x > sum) ^ (a[0] > a[n-1]) 決定移動左邊界還是右邊界
    if ((x > a[0] + a[n-1]) ^ (a[0] > a[n-1]))
        return judge_rec(a + 1, n - 1, x);  // 移動左
    else
        return judge_rec(a, n - 1, x);      // 移動右
}

// 迭代版 (更高效)
bool judge_iter(int *a, size_t n, int x) {
    while (n > 1) {
        if (x == a[0] + a[n-1]) return true;
        if ((x > a[0] + a[n-1]) ^ (a[0] > a[n-1])) {
            a++; n--;  // 移動左邊界
        } else {
            n--;       // 移動右邊界
        }
    }
    return false;
}

核心邏輯解析

陣列單調遞增：a[0] < a[n-1] 為真 (1)。若 x > sum 需增大和 → 移動左邊界 (a++)；(1) ^ (1) = 0 → 走 else 分支？錯！實際代碼中 ^ 結果為真時走 a++，故條件應為 (x > sum) ^ (a[0] > a[n-1]) 為真時移動左。
驗證：遞增陣列 a[0] < a[n-1] → (a[0] > a[n-1])=0。若 x > sum (1) ^ 0 = 1 → 移動左 ✓；若 x < sum (0) ^ 0 = 0 → 移動右 ✓。
遞減陣列同理可證。