java - ArrayDeque.allocateElements 的实现(按位运算)

Question

我在查看 Java 1.6 的 Java.Util.ArrayDeque(一个队列实现)的源代码时偶然发现了 allocateElements() ，它应该根据给定的元素数量调整后备数组的大小:

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];
}

将 initialCapacity 与 itself-rshifted 进行 ORing 的目的是什么？

Answer 1

为了简化 ArrayDeque 的实现，它看起来像 doubleCapacity() 长度“始终是二的幂”，它可以“在 addX() 方法中”被调用。特别是，

private void doubleCapacity() {
    ...
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    ...
}

附录:这是一个示例，它检查了在递增到下一个更大的 2 的幂之前临界值处的计算容量。

/** @see http://stackoverflow.com/questions/5528205 */
public class ArrayDequeCapacity {

    public static void main(String[] args) {
        for (int i = 1; i < 32; i++) {
            int n = (int) Math.pow(2, i) - 1;
            System.out.println(i + " " + n + " " + getCapacity(n));
        }
    }

    private static int getCapacity(int numElements) {
        int 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
        return initialCapacity;
    }
}

控制台:

1 1 22 3 43 7 84 15 165 31 326 63 647 127 1288 255 2569 511 51210 1023 102411 2047 204812 4095 409613 8191 819214 16383 1638415 32767 3276816 65535 6553617 131071 13107218 262143 26214419 524287 52428820 1048575 104857621 2097151 209715222 4194303 419430423 8388607 838860824 16777215 1677721625 33554431 3355443226 67108863 6710886427 134217727 13421772828 268435455 26843545629 536870911 53687091230 1073741823 107374182431 2147483646 1073741824