C語言位運算技巧：統計整數二進制中 1 的個數

Brian Kernighan 演算法：O(k) 時間計算 Hamming Weight

統計整數二進制表示中 1 的個數（人口計數），最優雅的解法是 n &= (n - 1) 迴圈，每次清除最低位的 1。

核心演算法

#include <stdio.h>

// 計算 1 的個數
int count_ones(int n) {
    int count = 0;
    while (n) {
        count++;
        n &= (n - 1); // 清除最低位的 1
    }
    return count;
}

int main() {
    printf("count(10)  = %d  // 1010 -> 2\n", count_ones(10));
    printf("count(0)   = %d  // 0 -> 0\n", count_ones(0));
    printf("count(-1)  = %d  // 全 1 (32位) -> 32\n", count_ones(-1));
    printf("count(255) = %d  // 11111111 -> 8\n", count_ones(255));
    return 0;
}

原理圖解

n = 10 (1010₂)
n-1 = 9  (1001₂)
n & (n-1) = 1000₂ (8)  ← 最低位 1 被清除

n = 8  (1000₂)
n-1 = 7  (0111₂)
n & (n-1) = 0000₂ (0)  ← 再次清除，結束

總計 2 次迴圈，對應 2 個 1

複雜度分析

變體與應用

1. 判斷是否為 2 的冪次

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}
// 只有 1 個 1 時，n & (n-1) 為 0

2. 計算兩數二進制不同位數（漢明距離）

int hammingDistance(int a, int b) {
    return count_ones(a ^ b); // 異或得出不同位，再計數
}

3. 反轉二進制位序列

unsigned int reverseBits(unsigned int n) {
    unsigned int rev = 0;
    for (int i = 0; i < 32; i++) {
        rev = (rev << 1) | (n & 1);
        n >>= 1;
    }
    return rev;
}

現代編譯器內建函數

// GCC/Clang
int count = __builtin_popcount(n);        // 32-bit
int count = __builtin_popcountll(n);      // 64-bit

// MSVC (intrin.h)
#include <intrin.h>
int count = __popcnt(n);                  // 需 POPCNT 指令集支援

硬體加速

• x86 POPCNT 指令 (SSE4.2, 2008+)：單指令完成
• ARM NEON：vcnt 向量計數指令
• RISC-V：cpop 擴展指令 (Zbb)

面試必考點總結

1. 理解 n & (n-1) 清除最低位 1 的原理
2. 能手寫 count_ones、isPowerOfTwo、hammingDistance
3. 知道編譯器內建函數與硬體指令的存在
4. 理解有號數右移的算術/邏輯位移差異