整數二進制中 1 的個數：位運算經典算法（Brian Kernighan 算法）

題目描述

輸入一個 32 位有符號整數，輸出其二進制補碼表示中 1 的個數。負數按補碼處理。

解法一：字符串轉換法（直觀但低效）

int count_ones_string(int n) {
    char buf[33];
    itoa(n, buf, 2);  // 非標準，或用 sprintf
    int cnt = 0;
    for (char *p = buf; *p; ++p)
        if (*p == '1') ++cnt;
    return cnt;
}

缺點：涉及除法/取模、字符串操作，速度慢，依賴庫函數。

解法二：Brian Kernighan 算法（教科書級位運算）

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

核心原理

n - 1 會將 n 最低位的 1 變為 0，該位右側所有 0 變為 1。n & (n-1) 精準清零最低位 1，其餘位不變。

n       = 1101000 (二進制)
n-1     = 1100111
n&(n-1) = 1100000  ← 最低位 1 被清零

循環次數恰好等於 1 的個數，平均 O(k)，k 為 1 的個數，最壞 O(32)。

解法三：查表法（極致性能）

static const unsigned char bits_in_byte[256] = {
    0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,  /* 0-15 */
    /* ... 至 255，可由腳本生成 */
};

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

無分支、固定 4 次查表，適合高頻調用場景（網絡包校驗、位圖索引）。

解法四：並行計數（SWAR 技術）

int count_ones_swar(unsigned int n) {
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555);  // 2-bit 計數
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);  // 4-bit 計數
    n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);  // 8-bit 計數
    n = (n * 0x01010101) >> 24;                      // 加總到最高位
    return n;
}

無查表、無分支、純 ALU 指令，現代 CPU 無分支預測失敗，極快。

性能對比（參考）

C++ 標準庫一行解決

#include <bit>  // C++20
int cnt = std::popcount(n);  // 編譯器內建指令，最優

GCC/Clang 內建：__builtin_popcount(n)（32位）、__builtin_popcountll(n)（64位）。

總結

1. 面試首選 Brian Kernighan 算法，代碼簡潔、原理清晰、性能優秀。
2. 工程上優先 std::popcount / __builtin_popcount，編譯器自動選擇硬件指令（POPCNT）。
3. 理解 n & (n-1) 還能解決「判斷 2 的冪次」、「提取最低位 1」等變體題。