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

调整后备数组的大小：What is the Purpose of ORinginitialCapacity with itself -r转移？

Answer 1

它看起来像 ArrayDeque< /a> 长度“始终是 2 的幂”，以简化可以“在 addX() 方法内”调用的 doubleCapacity() 的实现。特别是

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 2
2 3 4
3 7 8
4 15 16
5 31 32
6 63 64
7 127 128
8 255 256
9 511 512
10 1023 1024
11 2047 2048
12 4095 4096
13 8191 8192
14 16383 16384
15 32767 32768
16 65535 65536
17 131071 131072
18 262143 262144
19 524287 524288
20 1048575 1048576
21 2097151 2097152
22 4194303 4194304
23 8388607 8388608
24 16777215 16777216
25 33554431 33554432
26 67108863 67108864
27 134217727 134217728
28 268435455 268435456
29 536870911 536870912
30 1073741823 1073741824
31 2147483646 1073741824

Answer 2

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

等于：

    initialCapacity |= (initialCapacity >>>  1) | (initialCapacity >>>  2) |
                       (initialCapacity >>>  3) | (initialCapacity >>>  4) |
                       (initialCapacity >>>  5) | (initialCapacity >>>  6) |
                       (initialCapacity >>>  7) | (initialCapacity >>>  8) |
                       (initialCapacity >>>  9) | (initialCapacity >>>  10) |
                       (initialCapacity >>>  11) | (initialCapacity >>>  12) |
                       (initialCapacity >>>  13) | (initialCapacity >>>  14) |
                       (initialCapacity >>>  15) | (initialCapacity >>>  16) |
                       (initialCapacity >>>  17) | (initialCapacity >>>  18) |
                       (initialCapacity >>>  19) | (initialCapacity >>>  20) |
                       (initialCapacity >>>  21) | (initialCapacity >>>  22) |
                       (initialCapacity >>>  23) | (initialCapacity >>>  24) |
                       (initialCapacity >>>  25) | (initialCapacity >>>  26) |
                       (initialCapacity >>>  27) | (initialCapacity >>>  28) |
                       (initialCapacity >>>  29) | (initialCapacity >>>  30) |
                       (initialCapacity >>>  31)

它将把低于第一个的所有位设置为 1。