整數二進制中 1 的個數統計：三種高效位運算算法

整數二進制中 1 的個數統計：三種高效位運算算法

計算整數二進制表示中 1 的個數（即漢明重量，Hamming Weight）是經典面試題，也是位運算基本功的考察。本文介紹三種遞進優化的解法，並分析負數處理的陷阱。

題目描述

輸入一個整數，輸出其二進制表達中 1 的個數。例如輸入 10（二進制 1010），輸出 2。

解法一：右移檢查最低位（僅適用於非負數）

最直觀的思路：循環檢查最低位是否為 1，然後將數字右移一位，直到數字變為 0。

int NumberOf1_Solution1(int n) {
    int count = 0;
    while (n) {
        if (n & 1) count++;
        n = n >> 1; // 算術右移，負數會補 1 導致死循環
    }
    return count;
}

缺陷：對於負數（如 0x80000000），算術右移會在高位補 1，導致數值永遠不為 0，陷入死循環。且除法效率遠低於位移操作。

解法二：左移標誌位檢查（適用於所有整數）

不動被測數字，而是用一個標誌位從 1 開始左移，依次與輸入數字進行 AND 運算，檢查每一位。

int NumberOf1_Solution2(int n) {
    int count = 0;
    unsigned int flag = 1; // 必須用無符號數，避免左移溢出行為未定義
    while (flag) {
        if (n & flag) count++;
        flag = flag << 1;
    }
    return count;
}

循環固定執行 32 次（32 位整數），時間複雜度恆定，無死循環風險。

解法三：Brian Kernighan 算法（最優雅，時間複雜度 O(k)）

核心洞察：n & (n - 1) 會將 n 的二進制中最右邊的 1 翻轉為 0。

例如：n = 1100 (12)，n-1 = 1011 (11)，n & (n-1) = 1000 (8)。最右邊的 1 被清零。

一個數有多少個 1，就能執行多少次這個操作直到變為 0。

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

此法僅迴圈「1 的個數」次，對稀疏 1 的數字極快，且完美處理負數（補碼表示下邏輯一致）。

擴展應用：判斷 2 的冪次

若 n > 0 且 n & (n - 1) == 0，則 n 是 2 的整數次冪（二進制只有一個 1）。

補充：查表法（工程實用優化）

預計算 0~15 (4位) 的 1 的個數，每次查表 4 位，減少位運算開銷：

int countBits(int value) {
    int count = 0;
    int bits4[16] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
    while (value != 0) {
        count += bits4[value & 0xF];
        value >>= 4;
    }
    return count;
}

此法常用於嵌入式或高性能場景，平衡了代碼大小與執行速度。