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

时间:2022-03-03 15:09:43

在看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次幂)。