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

2018-07-13

在计算机中,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;
}

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

  1. n = 输入减 1

  2. 将 n 与自己(无符号)右移 1 位进行按位或,这样一来 n 的二进制形式中所有的 1 的右边一位被置为 1,即连续 2 位为 1

  3. 将 n 与自己(无符号)右移 2 位进行按位或,同样的原理,连续 4 位为 1

  4. 以此类推,直到与右移 16 位按位或后停止,由于 Java 中 int 类型为 32 位,这样 n 的二进制形式的最高位 1 之后的所有位全部被置为 1

  5. n + 1 得到 2 的幂

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

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

算法哈希表
知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

Linux 折腾手记

通配符匹配 Wildcard Matching