C語言計算兩數二進制不同位數：模除法與位運算法雙實作

問題

輸入兩整數 m, n，統計其 32 位二進制表示中不同位的個數（漢明距離）。

方法一：模除法（教學用）

#include 

int main() {
    int m, n, count = 0;
    printf("請輸入 m,n: ");
    scanf("%d%d", &m, &n);
    for (int i = 31; i >= 0; i--) {
        int x = m % 2; m /= 2;
        int y = n % 2; n /= 2;
        if (x != y) count++;
    }
    printf("不同的 bit 位有 %d 個\n", count);
    system("pause");
    return 0;
}

缺點：修改了原變數 m,n；效率較低。

方法二：位運算法（推薦）

#include 

int main() {
    int m, n;
    printf("請輸入 m,n: ");
    scanf("%d%d", &m, &n);
    int diff = m ^ n;           // 異或：不同位為 1
    int count = 0;
    while (diff) {
        count += diff & 1;      // 檢查最低位
        diff >>= 1;             // 右移
    }
    printf("不同的 bit 位有 %d 個\n", count);
    system("pause");
    return 0;
}

核心技巧

• m ^ n：相同為 0，不同為 1，直接得到差異位掩碼。
• diff & 1 + diff >>= 1：逐位計數（亦可用 __builtin_popcount 或 diff &= diff-1 清除最低 1 位加速）。

進階：Kernighan 演算法

while (diff) {
    count++;
    diff &= diff - 1;   // 每次清除最低位的 1
}

迴圈次數等於 1 的個數，最快。