C 語言位運算面試題：統計二進制中 1 的個數（兩種高效算法）

方法一：逐位檢查（基礎版）

int countOnes(unsigned int n) {
    int cnt = 0;
    while (n) {
        cnt += n & 1; // 最低位是否為 1
        n >>= 1;      // 右移一位
    }
    return cnt;
}

方法二：Brian Kernighan 算法（極快，O(1 的個數)）

int countOnes(unsigned int n) {
    int cnt = 0;
    while (n) {
        n &= (n - 1); // 清除最低位的 1
        cnt++;
    }
    return cnt;
}

原理解析

n-1 將最低位 1 變 0，低位 0 變 1。n & (n-1) 精準清除最低位 1。循環次數等於 1 的個數，而非位寬。

n = 101100
n-1 = 101011
n&(n-1) = 101000  (最低位 1 被清除)

完整測試代碼

#include <stdio.h>

int countOnes(unsigned int n) {
    int cnt = 0;
    while (n) { n &= n-1; cnt++; }
    return cnt;
}

int main() {
    unsigned int x;
    while (scanf("%u", &x) == 1)
        printf("count=%d\n", countOnes(x));
    return 0;
}

運行示例

15
count=4

15 = 1111b 有 4 個 1。

工程建議

• 現代編譯器提供內建函數 __builtin_popcount (GCC/Clang)，單指令實現，首選；
• 面試手寫時，Brian Kernighan 算法展示位運算功力；
• 參數用 unsigned 避免負數右移實現定義行為差異。