第一个大于等于某个正整数的 2 的幂

在计算机中，2 的幂是神奇的数，很多运算可以用位操作来完成。

求第一个大于等于某个正整数的 2 的幂，例如 1023 则返回 1024，这个算法在 Java 中哈希表分配桶就有所运用。

容易想到的一个实现是将 2 的幂一个个拿来比较，不过看起来不够优雅。

Java 源码给出了位运算的实现：

/**
 * Returns a power of two size for the given target capacity.
 */
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;
}

咋一看有点懵逼，实际上非常简单，分析一下它做了什么事情：

n = 输入减 1
将 n 与自己（无符号）右移 1 位进行按位或，这样一来 n 的二进制形式中所有的 1 的右边一位被置为 1，即连续 2 位为 1
将 n 与自己（无符号）右移 2 位进行按位或，同样的原理，连续 4 位为 1
以此类推，直到与右移 16 位按位或后停止，由于 Java 中 int 类型为 32 位，这样 n 的二进制形式的最高位 1 之后的所有位全部被置为 1
n + 1 得到 2 的幂

为什么一开始要将 n 置为输入减 1 呢？这是为了处理输入恰好为 2 的幂的 corner case，这种情况下如果不减 1 的话，得到的就是大于输入的 2 的幂了，而期望输出值应该是输入本身。

例如输入为 8，16 进制形式为 0x00000008，如果不减 1，将最高位 1 之后位都置为 1，得到 0x0000000f，加 1 得 0x00000010，输出值为 16，而期望输出的是 8。