C語言位運算經典：找出陣列中唯一出現一次的數字 (XOR 消除法)

編輯：關於C語言

C語言位運算經典：找出陣列中唯一出現一次的數字 (XOR 消除法)

**問題**：陣列中除一個數字出現一次外，其餘數字均出現**兩次**。找出該唯一數字。要求 O(n) 時間、O(1) 空間。

核心原理：XOR 性質

x ^ x = 0 (相同為 0)
x ^ 0 = x (與 0 異或不變)
x ^ y = y ^ x (交換律)
(x ^ y) ^ z = x ^ (y ^ z) (結合律)

成對出現的數字兩兩 XOR 抵消為 0，剩下的即為唯一數字。

完整程式碼

#include <stdio.h>

int find_single(int *arr, int len) {
    int result = 0;
    for (int i = 0; i < len; i++) {
        result ^= arr[i];
    }
    return result;
}

int main() {
    int arr[] = {1, 3, 3, 1, 4, 9, 4, 5, 5};
    int len = sizeof(arr) / sizeof(arr[0]);
    
    int single = find_single(arr, len);
    printf("唯一出現一次的數字：%d\n", single);  // 9
    
    return 0;
}

執行過程演示

初始：result = 0
0 ^ 1 = 1
1 ^ 3 = 2
2 ^ 3 = 1
1 ^ 1 = 0
0 ^ 4 = 4
4 ^ 9 = 13
13 ^ 4 = 9
9 ^ 5 = 12
12 ^ 5 = 9  ← 最終結果

執行結果

唯一出現一次的數字：9

進階變體與解法

變體	條件	解法	複雜度
單一唯一，其餘出現 2 次	本題	XOR 全陣列	O(n) / O(1)
單一唯一，其餘出現 3 次	位計數法	32 位計數器取模 3	O(32n) / O(1)
兩個唯一，其餘出現 2 次	分組 XOR	找異或結果的任一 1 位分組	O(n) / O(1)
單一出現 k 次，其餘 m 次	通用位計數	每位計數取模 m	O(32n) / O(1)

變體二：其餘出現 3 次，位計數法實現

int find_single_3(int *arr, int len) {
    int count[32] = {0};
    for (int i = 0; i < len; i++) {
        for (int b = 0; b < 32; b++) {
            if (arr[i] & (1 << b)) count[b]++;
        }
    }
    int result = 0;
    for (int b = 0; b < 32; b++) {
        if (count[b] % 3) result |= (1 << b);
    }
    return result;
}

變體三：兩個唯一數字，分組 XOR

void find_two_single(int *arr, int len, int *a, int *b) {
    int xor_all = 0;
    for (int i = 0; i < len; i++) xor_all ^= arr[i];
    
    // 找到 xor_all 中任一為 1 的位 (lowbit)
    int diff_bit = xor_all & (-xor_all);
    
    *a = 0; *b = 0;
    for (int i = 0; i < len; i++) {
        if (arr[i] & diff_bit) *a ^= arr[i];
        else *b ^= arr[i];
    }
}