在看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。如下图所示:
解释下第一个位操作:
initialCapacity |= (initialCapacity >>> 1);
先将initialCapacity 逻辑右移一位(高位补0),再与initialCapacity 做位或,这样就将initialCapacity最高位1的下一位也变为了1,如下:
接下来的第二句位操作
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次幂)。