C 語言位運算技巧：計算兩數二進制不同位數

C 語言位運算技巧：計算兩數二進制不同位數

兩數對應位不同 ⇔ 異或結果為 1。統計 a ^ b 中 1 的個數即為漢明距離。

實作程式碼

#include <stdio.h>

int hamming_distance(int a, int b) {
    int diff = a ^ b;
    int count = 0;
    while (diff) {
        count++;
        diff &= (diff - 1); // 清除最低位 1 (Brian Kernighan 演算法)
    }
    return count;
}

int main() {
    printf("3(011) vs 5(101) -> %d\n", hamming_distance(3, 5)); // 2
    printf("10 vs 10 -> %d\n", hamming_distance(10, 10));       // 0
    printf("-1 vs 0 -> %d\n", hamming_distance(-1, 0));         // 32 (全1 vs 全0)
    return 0;
}

核心技巧：n & (n-1) 清除最低位 1

n      = 0010 1100
n - 1  = 0010 1011
n & (n-1) = 0010 1000  → 最低位 1 被清零

• 迴圈次數 = 1 的個數，最壞 32 次 (32-bit)，平均 16 次。
• 無分支預測失敗，效能極佳。

硬體加速

• x86 SSE4.2: _mm_popcnt_u32 (POPCNT 指令)。
• GCC/Clang: __builtin_popcount(a ^ b) 自動使用硬體指令或軟體模擬。
• C++20: std::popcount(a ^ b) (<bit>)。

應用場景