C語言統計兩數二進制不同位數：異或+計數經典算法

C語言統計兩數二進制不同位數：異或+計數經典算法

給定兩個 32 位整數 m、n，求其二進制表示中不同位的個數。核心思路：m ^ n 得到差異位掩碼，統計其中 1 的個數。

算法步驟

1. diff = m ^ n：異或運算，相同為 0，不同為 1
2. 統計 diff 中 1 的個數（Hamming Weight）

三種計數方法對比

#include <stdio.h>

// 方法 1：模 2 除法（最慢，教學用）
int count_ones_mod(int x) {
    int count = 0;
    while (x) {
        count += x % 2;
        x /= 2;
    }
    return count;
}

// 方法 2：位與 1（標準，O(位數)）
int count_ones_bitwise(int x) {
    int count = 0;
    while (x) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

// 方法 3：Brian Kernighan 算法（最優，O(1的個數)）
int count_ones_bk(int x) {
    int count = 0;
    while (x) {
        x &= x - 1;  // 清除最低位的 1
        count++;
    }
    return count;
}

int main() {
    int m = 1999;  // 011111001111
    int n = 2299;  // 100011111011
    int diff = m ^ n;  // 111100110100
    
    printf("異或結果：%d (0x%X)\n", diff, diff);
    printf("方法1：%d\n", count_ones_mod(diff));
    printf("方法2：%d\n", count_ones_bitwise(diff));
    printf("方法3：%d\n", count_ones_bk(diff));
    return 0;
}

運行結果

異或結果：3892 (0xF34)
方法1：7
方法2：7
方法3：7

Brian Kernighan 算法原理

x      = 10110100
x - 1  = 10110011
x&(x-1)= 10110000  // 最低位 1 變 0，其它不變
每次循環清除一個 1，循環次數 = 1 的個數

內建函數優化（GCC/Clang）

int count = __builtin_popcount(m ^ n);  // 編譯器優化為單指令 (POPCNT)

應用場景

• 漢明距離計算（編碼理論、錯誤檢測）
• 相似度比較（指紋、特征向量）
• 位板棋牌遊戲狀態差異
• 網絡路由前綴匹配