C語言統計二進制中 1 的個數：從朴素到 Brian Kernighan 算法優化

C語言統計二進制中 1 的個數：從朴素到 Brian Kernighan 算法優化

統計整數二進制表示中 1 的個數（Hamming Weight / Population Count）是經典位運算問題。本文展示三種算法的演進與優化。

算法演進

第一版：模 2 除法（朴素，慢）

int count_ones_v1(int n) {
    int count = 0;
    while (n != 0) {
        if (n % 2 == 1) count++;
        n /= 2;
    }
    return count;
}

缺點：除法慢，處理負數需注意（算術右移保留符號位）。

第二版：位與 1 + 右移（標準，O(位數)）

int count_ones_v2(int n) {
    int count = 0;
    while (n != 0) {
        count += n & 1;
        n >>= 1;  // 無符號右移更安全
    }
    return count;
}

仍需遍歷所有位（含前導 0）。

第三版：Brian Kernighan 算法（最優，O(1的個數)）

int count_ones_v3(int n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;  // 神奇操作：清除最低位的 1
        count++;
    }
    return count;
}

核心技巧原理

n      = xxxxxx1000  (最低位 1 後全 0)
n - 1  = xxxxxx0111  (最低位 1 變 0，後面全變 1)
n&(n-1)= xxxxxx0000  (最低位 1 被清除，高位不變)
每次循環消除一個 1，循環次數 = 1 的總數

性能對比 (測試 0xFFFFFFFF，32 個 1)

處理負數的正確姿勢

// 統一用無符號類型
int count_ones_unsigned(unsigned int n) {
    int count = 0;
    while (n) {
        n &= n - 1;
        count++;
    }
    return count;
}

// 或轉換調用
int count_ones_signed(int n) {
    return count_ones_unsigned((unsigned int)n);
}

查表法優化（查 8 位，4 次查表）

static const uint8_t table[256] = {
    0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,  // 0-15
    // ... 其餘 240 項預計算
};

int count_ones_lookup(unsigned int n) {
    return table[n & 0xFF] +
           table[(n >> 8) & 0xFF] +
           table[(n >> 16) & 0xFF] +
           table[(n >> 24) & 0xFF];
}