JDK 原碼閱讀筆記：BitSet.bitLen() — 見過最長的三元運算式鏈

背景

java.util.BitSet 內部方法 bitLen(int w) 計算整數二進位表示的有效位長（最高位 1 的位置+1）。實現採用二分決策樹，將 32 位空間層層折半，極致優化分支預測。

原碼重現（格式化後）

private static int bitLen(int w) {
    // Binary search - decision tree (5 tests, rarely 6)
    return
        (w < 1 << 15 ?
            (w < 1 << 7 ?
                (w < 1 << 3 ?
                    (w < 1 << 1 ? (w < 1 << 0 ? (w < 0 ? 32 : 0) : 1) : (w < 1 << 2 ? 2 : 3)) :
                    (w < 1 << 5 ? (w < 1 << 4 ? 4 : 5) : (w < 1 << 6 ? 6 : 7))) :
                (w < 1 << 11 ?
                    (w < 1 << 9 ? (w < 1 << 8 ? 8 : 9) : (w < 1 << 10 ? 10 : 11)) :
                    (w < 1 << 13 ? (w < 1 << 12 ? 12 : 13) : (w < 1 << 14 ? 14 : 15)))) :
            (w < 1 << 23 ?
                (w < 1 << 19 ?
                    (w < 1 << 17 ? (w < 1 << 16 ? 16 : 17) : (w < 1 << 18 ? 18 : 19)) :
                    (w < 1 << 21 ? (w < 1 << 20 ? 20 : 21) : (w < 1 << 22 ? 22 : 23))) :
                (w < 1 << 27 ?
                    (w < 1 << 25 ? (w < 1 << 24 ? 24 : 25) : (w < 1 << 26 ? 26 : 27)) :
                    (w < 1 << 29 ? (w < 1 << 28 ? 28 : 29) : (w < 1 << 30 ? 30 : 31)))));
}

設計精妙之處

• 無分支預測失誤：決策樹深度固定（5-6 次比較），CPU 流水線極友好
• 常數時間複雜度：O(1) 硬體級效能，無迴圈、無查表
• 邊界處理：w < 0 直接回傳 32（負數最高位為 1）
• 位移操作：1 << n 構造 2ⁿ 邊界值，零開銷

對比：通用實現

// 一般寫法：迴圈或查表
int len = 0;
while (w != 0) { w >>>= 1; len++; }
return len;

// 或 JDK 8+ Integer.numberOfLeadingZeros()
return 32 - Integer.numberOfLeadingZeros(w);

現代 JDK 已改用內建指令，但此決策樹仍是演算法教科書級範例，展示如何在無硬體支援下榨乾效能。