您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言位運算：計算兩整數二進制不同位的個數

編輯：關於C

漢明距離計算：異或 + 人口計數

計算兩個整數在二進制表示下不同位的個數，即漢明距離。核心技巧：a ^ b 得出不同位位置，再統計 1 的個數。

完整實作

#include <stdio.h>

// 計算不同位個數（漢明距離）
int hammingDistance(int a, int b) {
    int diff = a ^ b;      // 異或：相同為 0，不同為 1
    int count = 0;
    while (diff) {
        count++;
        diff &= (diff - 1); // 清除最低位 1
    }
    return count;
}

int main() {
    // 3 = 0011₂, 5 = 0101₂
    // 異或 = 0110₂ -> 兩個 1
    printf("hammingDistance(3, 5) = %d\n", hammingDistance(3, 5));
    
    // 更多測試
    printf("hammingDistance(0, 0)   = %d\n", hammingDistance(0, 0));   // 0
    printf("hammingDistance(1, 2)   = %d\n", hammingDistance(1, 2));   // 2 (01 vs 10)
    printf("hammingDistance(255, 0) = %d\n", hammingDistance(255, 0)); // 8
    printf("hammingDistance(-1, 0)  = %d\n", hammingDistance(-1, 0));  // 32 (全1 vs 全0)
    
    return 0;
}

異或運算性質回顧

應用場景

錯誤檢測/修正碼：海明碼、CRC 校驗
密碼學：差分分析、側信道攻擊抗性評估
資料壓縮：相似度檢測、去重
機器學習：局部敏感雜湊 (LSH)、相似度搜尋
網路路由：BGP 路徑屬性比較

硬體加速版本

// GCC/Clang 內建
int hammingDistanceFast(int a, int b) {
    return __builtin_popcount(a ^ b);
}

// C++20 標準庫
#include <bit>
int hammingDistanceCpp20(int a, int b) {
    return std::popcount(a ^ b);
}

// 手動展開優化 (無內建函數時)
int hammingDistanceManual(int a, int b) {
    int x = a ^ b;
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x3F;
}

擴展：64 位元與任意長度

// 64-bit 版本
long long hammingDistance64(long long a, long long b) {
    return __builtin_popcountll(a ^ b);
}

// 任意長度位元組陣列
int hammingDistanceBytes(const unsigned char *a, const unsigned char *b, size_t len) {
    int dist = 0;
    for (size_t i = 0; i < len; i++) {
        dist += __builtin_popcount(a[i] ^ b[i]);
    }
    return dist;
}