整數二進制中 1 的個數統計：位運算與 Brian Kernighan 算法性能對比 (Java)

問題

計算 32 位整數二進制表示中 1 的個數。比較兩種方法的運行時間：

1. 位運算並行累加法：利用掩碼分治 (0x55555555, 0x33333333 ...)。
2. Brian Kernighan 算法：x &= (x-1) 每次消除最低位 1。

代碼實現 (Java)

public class BitCount {
    // 方法一：位運算並行累加
    public static int countOne(int x) {
        x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
        x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
        x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
        x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
        x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
        return x;
    }

    // 方法二：Brian Kernighan
    public static int countOne2(int x) {
        int cnt = 0;
        while (x != 0) {
            x &= (x - 1);
            cnt++;
        }
        return cnt;
    }

    public static void main(String[] args) {
        long t1 = System.currentTimeMillis();
        for (int i = -10000000; i < 10000000; i++) countOne(i);
        long t2 = System.currentTimeMillis();
        long t3 = System.currentTimeMillis();
        for (int i = -10000000; i < 10000000; i++) countOne2(i);
        long t4 = System.currentTimeMillis();
        System.out.println((t2-t1) + " ---- " + (t4-t3));
    }
}

測試結果分析

運行 2×10⁷ 次循環：

• 位運算法：約 150~200 ms（有波動）。
• Kernighan 法：穩定在 250~270 ms。

結論：位運算並行累加法整體更快，且無分支預測失敗，適合高性能場景。Kernighan 法在 1 的個數較少時較快，但最壞情況 (全 1) 需 32 次循環。

補充

代碼中註釋的 (3) x = (x * 0x01010101) >> 24 也可替代最後兩步，利用乘法加速求和。