Java 遞歸計算二進制中 1 的個數：多種實現與優化技巧

計算整數二進制表示中 1 的個數（Hamming Weight / Population Count）是經典面試題，也是位運算基礎應用。本文從遞歸思維出發，逐步演進到位運算優化與內建方法，幫你建立完整解題框架。

遞歸核心邏輯

觀察規律：奇數的 1 個數 = (n>>1) 的 1 個數 + 1；偶數則直接右移直到遇到奇數或 0。這正是遞歸的「遞推關係」。

public static int countOnesRecursive(int n) {
    if (n == 0) return 0;                    // 基礎情況
    if ((n & 1) == 1) return countOnesRecursive(n >> 1) + 1; // 奇數
    return countOnesRecursive(n >> 1);       // 偶數
}

迭代優化：Brian Kernighan 算法

n & (n-1) 能將最低位的 1 翻為 0，循環次數等於 1 的個數，極其高效：

public static int countOnesBitTrick(int n) {
    int cnt = 0;
    while (n != 0) {
        n &= (n - 1);
        cnt++;
    }
    return cnt;
}

JDK 內建最佳解

生產環境請直接使用 Integer.bitCount(int)，JVM 會內建為硬體指令（POPCNT），效能最強：

int ones = Integer.bitCount(13); // 3

擴展：長整數與任意精度

• Long.bitCount(long) 處理 64 位
• BigInteger.bitCount() 支援任意大整數

效能對比與選型建議

總結

理解遞歸與位運算的底層邏輯是功力體現，但實際開發請毫不猶豫選用 Integer.bitCount()。若面試要求手寫，Kernighan 算法兼具優雅與高效，是標準答案首選。