位運算技巧：找出數組中出現一次的數字（單數與雙數變體）

問題 1：只有一個數字出現一次，其餘均出現兩次

利用異或（XOR）運算的性質：

• a ^ 0 = a
• a ^ a = 0
• 異或滿足交換律與結合律

將數組所有元素依次異或，成對出現的數字抵消為 0，最終結果即為那個唯一的數字。

代碼實現

int findSingle(int arr[], int n) {
    int res = 0;
    for (int i = 0; i < n; ++i) {
        res ^= arr[i];
    }
    return res;
}

時間複雜度 O(n)，空間複雜度 O(1)。

問題 2：有兩個數字出現一次，其餘均出現兩次

思路：將數組分為兩組，使得這兩個唯一數字分落在不同組內，每組內其餘數字仍成對出現，轉化為問題 1 求解。

關鍵步驟：找到分組依據

1. 先將所有數字異或，得到 xorAll = a ^ b（a、b 為兩個唯一數字）。
2. xorAll 中至少有一位為 1（因為 a ≠ b）。取 xorAll 的最低位 1 作為分組標誌：mask = xorAll & (-xorAll)。
3. 遍歷數組，根據 (num & mask) != 0 分為兩組，分別異或，即得到 a 和 b。

優化版代碼（O(1) 空間）

void findTwoSingles(int num[], int n) {
    int xorAll = 0;
    for (int i = 0; i < n; ++i) xorAll ^= num[i];

    int mask = xorAll & (-xorAll); // 取最低位 1
    int a = 0, b = 0;
    for (int i = 0; i < n; ++i) {
        if (num[i] & mask) a ^= num[i];
        else             b ^= num[i];
    }
    printf("%d %d\n", a, b);
}

原理解析：x & -x 為何能取最低位 1？

負數在計算機中以補碼表示：-x = ~x + 1。
最低位 1 及其右側所有位在 x 和 -x 中相反，左側相同。因此 x & -x 只保留最低位 1。
例：4 (0100) & -4 (1100) = 0100；1000 (1111101000) & -1000 = 1000。

總結對比

位運算是處理「成對抵消」類問題的利器，掌握 x & -x 取最低位 1 的技巧，能輕鬆解決多數字唯一值查找問題。