C 語言按位異或實戰：O(N) 找出陣列中唯一出現一次的數字

C 語言按位異或實戰：O(N) 找出陣列中唯一出現一次的數字

題目：陣列中只有一個數字出現一次，其餘皆成對出現。要求 O(N) 時間、O(1) 空間找出該數字。

一、 核心原理

異或（^）性質：

• x ^ x = 0（相同歸零）
• x ^ 0 = x（保留）
• 滿足交換律、結合律

成對數字異或結果為 0，全陣列異或後，成對者抵消，單一者保留。

二、 代碼實現

#include <stdio.h>

int main() {
    int arr[] = {1,2,3,4,5,6,1,2,3,4,5,6,7};
    int len = sizeof(arr)/sizeof(arr[0]);
    int res = 0;
    for (int i = 0; i < len; i++) res ^= arr[i];
    printf("%d\n", res); // 輸出 7
    return 0;
}

三、 複雜度

• 時間：O(N)，單趟掃描。
• 空間：O(1)，僅 1 個變量。

四、 擴展

• 若有兩個出現一次的數字：全陣列異或得 a^b，取最低位 1 分組，各組異或得 a、b（見上文進階版）。
• 若出現 3 次 vs 1 次：需位計數器（每位模 3），或有限狀態機。

異或是位運算中最優雅的「配對消除」工具，面試高頻必考。