位運算技巧：O(1) 計算不小於給定數的最小 2 的冪次（Round Up To Power Of Two）

問題描述

給定無符號整數 x，求最小的 2^n ≥ x。例：63→64, 64→64, 100→128。

核心位運算技巧：Smear 高位至低位

將最高位 1 向右「塗抹」到所有低位，然後 +1 得到下一個 2 的冪次。若輸入本身是 2 的冪次，先 x-- 保證結果不變。

標準實現（32 位整數）

// Android Collections.roundUpToPowerOfTwo
public static int roundUpToPowerOfTwo(int i) {
    i--;
    i |= i >>> 1;  // 無符號右移
    i |= i >>> 2;
    i |= i >>> 4;
    i |= i >>> 8;
    i |= i >>> 16;
    return i + 1;
}

// JDK HashMap.tableSizeFor (Java 8+)
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

JDK 額外處理 n < 0（輸入過大導致符號位變 1）和容量上限 MAXIMUM_CAPACITY = 1<<30。

64 位擴展