Implementation of ArrayDeque.allocateElements (bitwise operations)

Question

I was looking at the source of Java 1.6's Java.Util.ArrayDeque (a queue implementation) and stumbled on allocateElements() which should size the backing array according to the given number of elements:

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 ORing initialCapacity with itself-rshifted?

Answer 1

It looks like the ArrayDeque length "is always a power of two" in order to simplify the implementation of doubleCapacity(), which may be invoked "within an addX() method." In particular,

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

Addendum: Here's an example that examines the calculated capacity at critical values just before incrementing to the next larger power of two.

/** @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;
    }
}

Console:

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);

equals to:

    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)

It will set all bits lower than the first to 1.