找到大于一个正整数N的最小2的次幂数

在看JDK1.7中ArrayDeque源码时，有一个函数是这样写的：

 private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        elements = (E[]) new Object[initialCapacity];
    }

其中的if区域是为了找到大于numElements的最小2的次幂数，它是用移位、位或操作完成的。

            initialCapacity |= (initialCapacity >>> 1);
            initialCapacity |= (initialCapacity >>> 2);
            initialCapacity |= (initialCapacity >>> 4);
            initialCapacity |= (initialCapacity >>> 8);
            initialCapacity |= (initialCapacity >>> 16);

上面这段代码的效果是将initialCapacity 的最高位1的所有低位全部变为1。如下图所示：
找到大于一个正整数N的最小2的次幂数

解释下第一个位操作：

 initialCapacity |= (initialCapacity >>> 1);

先将initialCapacity 逻辑右移一位（高位补0），再与initialCapacity 做位或，这样就将initialCapacity最高位1的下一位也变为了1，如下：

找到大于一个正整数N的最小2的次幂数

接下来的第二句位操作

 initialCapacity |= (initialCapacity >>> 2);

会将initialCapacity最高位1的下面3位都变为了1。

由于在java中整型是固定的32位，所以这5次位操作后，initialCapacity最高位1的所有低位全部也变为1。然后再执行

            initialCapacity++;

就会得到大于initialCapacity的最小2的次幂数。

有一个特殊情况需要处理，即initialCapacity的最高位1是在第31位上：
01XXXXXX XXXXXXXX XXXXXXXX XXXXXXXX，这样在进行所有操作后initialCapacity会变为：
10000000 00000000 00000000 00000000，最高位为1，实际上就上溢为一个负数。为了处理这种情况，会将initialCapacity右移一位，这样它就变为了一个很大的整数（2的30次幂）。

秒客网

找到大于一个正整数N的最小2的次幂数

相关文章