Java 高效計算二進制中 1 的個數：Brian Kernighan 演算法

演算法核心

Brian Kernighan 演算法利用位元運算特性：n & (n - 1) 會清除 n 二進制表示中 最低位的 1。重複執行直到 n == 0，迴圈次數即為 1 的個數。

範例追蹤

n = 14 (1110₂)

1. 14 & 13 = 12 (1100₂) → count=1
2. 12 & 11 = 8 (1000₂) → count=2
3. 8 & 7 = 0 → count=3

結果：3 個 1。迴圈次數等於 1 的個數，而非位寬，對稀疏 1 極其高效。

Java 實作

package algorithm;

public class BitCount {
    public static void main(String[] args) {
        int[] test = {0, 1, 7, 14, 255, 1024, Integer.MAX_VALUE};
        for (int n : test) {
            System.out.printf("%d (0x%X) -> %d ones%n", n, n, countOnes(n));
        }
    }

    /**
     * 計算整數二進制中 1 的個數
     * 時間複雜度：O(k)，k = 1 的個數
     * 空間複雜度：O(1)
     */
    public static int countOnes(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
}

替代方案比較

擴充：long 版本與負數處理

public static int countOnesLong(long n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}
// Java 整數為補碼表示，負數最高位為 1，演算法同樣適用
// 例：-1 (0xFFFFFFFF) -> 32 個 1

總結

Brian Kernighan 演算法是位元運算教科書級範例，展現「n & (n-1) 清除最低位 1」的巧思。實際開發中，請直接使用 Integer.bitCount() / Long.bitCount()，由 JVM 內建最佳化（硬體指令或查表），既簡潔又高效。

1. 上一篇文章： Apache Commons Net 實現 FTP 斷點續傳上傳下載
2. 下一篇文章： Java 遞歸解決漢諾塔問題：完整步驟與移動次數分析

Java 相關知識

主流開源 Java EE 應用伺服器橫向評測：JBoss 4.2、Geronimo 2、Tomcat 6 特性、部署與效能比較

對比 JBoss 4.2、Geronimo 2、Tomcat

深入理解 JSF 作用域與受管 Bean：請求、會話、應用層級資料管理

核心概念：三大作用域的生命週期與適用場景 在 JSF 應用中

Java IO 基礎：File 類文件與目錄操作全攻略

File 類定位 java.io.File 代表文件系統中的

使用 Eclipse Europa 進行 Web 開發（三）：Ruby Development Toolkit 與 RadRails

系列簡介 身為 Web 開發人員，現在是最好的時代。從未有過