C 語言位運算經典練習：異或找單一/雙單一數字、二進制翻轉、無溢位平均值

C 語言位運算經典練習：異或找單一/雙單一數字、二進制翻轉、無溢位平均值

位運算是 C 語言高效編程的利器。本文匯總 5 道經典練習：異或找出現一次的數字、進階版找兩個出現一次的數字、32 位整數二進制翻轉、不溢位求平均值、統計二進制 1 的個數。

一、 異或找單一出現數字（其餘成對）

性質：x ^ x = 0、x ^ 0 = x、滿足交換/結合律。成對數字異或歸零，單一者保留。

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

二、 進階：找兩個出現一次的數字（其餘成對）

1. 全陣列異或 → 得 xor_all = a ^ b（a,b 為兩目標），xor_all != 0。
2. 找 xor_all 最低位 1：mask = xor_all & (-xor_all)。
3. 按 mask 分組：該位為 1 進組 A，為 0 進組 B。a,b 落入不同組，組內其餘成對。
4. 各組異或 → 得 a、b。

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];
    int mask = xor_all & -xor_all; // 取最低位 1
    *a = *b = 0;
    for (int i = 0; i < len; i++) {
        if (arr[i] & mask) *a ^= arr[i];
        else *b ^= arr[i];
    }
}

三、 32 位無符號整數二進制翻轉

25 (000...00011001) → 2550136832 (10011000...000)。

uint32_t reverse_bits(uint32_t x) {
    uint32_t rev = 0;
    for (int i = 0; i < 32; i++) {
        rev = (rev << 1) | (x & 1);
        x >>= 1;
    }
    return rev;
}

四、 無溢位求兩整數平均值

(a+b)/2 可能溢位。利用位運算分解：

int avg_no_overflow(int a, int b) {
    return (a & b) + ((a ^ b) >> 1);
}
// 原理：a&b 為共同 1 位（進位部分），a^b 為不同位（無進位和），右移 1 相當於除 2。

五、 統計二進制中 1 的個數（Brian Kernighan 算法）

int count_ones(uint32_t x) {
    int cnt = 0;
    while (x) { x &= (x - 1); cnt++; } // 每次清除最低位 1
    return cnt;
}

六、 總結

位運算核心性質：& 取位/清零、| 置位、^ 翻轉/無進位加、~ 取反、<<>> 乘除 2 的冪次。掌握 x & (x-1) 清除最低位 1、x & -x 取最低位 1、異或消除成對、分組異或解耦兩目標，即可破解絕大多數位運算面試題。