ArrayDeque中allocateElements的分析

最近看了下ArrayDeque的源码，发现一个东西很有意思，之前也看到了，没有细想，现在仔细看了看，决定写下来。

/**
     * The array in which the elements of the deque are stored.
     * The capacity of the deque is the length of this array, which is
     * always a power of two. The array is never allowed to become
     * full, except transiently within an addX method where it is
     * resized (see doubleCapacity) immediately upon becoming full,
     * thus avoiding head and tail wrapping around to equal each
     * other.  We also guarantee that all array cells not holding
     * deque elements are always null.
     */
    transient Object[] elements; // non-private to simplify nested class access
 /**
     * The minimum capacity that we'll use for a newly created deque.
     * Must be a power of 2.
     */
    private static final int MIN_INITIAL_CAPACITY = 8;

    // ******  Array allocation and resizing utilities ******

    /**
     * Allocates empty array to hold the given number of elements.
     *
     * @param numElements  the number of elements to hold
     */
    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 = new Object[initialCapacity];
    }

/**
     * Doubles the capacity of this deque.  Call only when full, i.e.,
     * when head and tail have wrapped around to become equal.
     */
    private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }

这是ArrayDeque在调用传入指定数量的构造方法的时候会调用的方法，目的是分配一个合适长度的数组供使用，所以其实这个方法就是为了分配合适数量的数组。

    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }

其实ArrayDeque来做扩容的时候都是通过doubleCapacity()方法来做的，ArrayDeque的容量只允许是2的倍数，那我们看上面我们要指定一个数来做构造方法的时候，ArrayDeque是怎么保证elements既是2的倍数又能够装起来我们需要的元素的？
这就是allocateElements这个方法要做的了。
主要的代码就是

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

我们知道>>>是无符号右移，高位补零。|是或操作，0|0=0否则为1。
我们来看initialCapacity |= (initialCapacity >>> 1);
也就是initialCapacity = initialCapacity | (initialCapacity >>> 1);
怎么来理解这个操作，自己或上自己右移一位，费解~
其实我们这么想，不管initialCapacity是几，所有的数最高位一定是1，比如
8 -> 1000
8>>>1 -> 0100
8|(8>>>1) -> 1100
其实从这个例子我们就可以看出来规律，只要这个数二进制大于两位，经过initialCapacity |= (initialCapacity >>> 1);高位总是会变成11xxxxxx,那后面的几步操作就好理解了。
我们用一个极端的例子来看，我们设置initialCapacity为Integer.MAX_VALUE >> 2，也就是1073741824，它的二进制是1000000000000000000000000000000。

运算完的结果就是全是1，有多少位就是多少个1，所以说8到15之间，运算完的结果都是1111，然后执行initialCapacity++; ，结果就是10000了，所以ArrayDeque的默认capacity是16。
所以说只要是32位以内，不管什么数都可以搞定。起决定性作用的只是你int值最高位的那个1罢了。
还有几个小细节要注意：
1、java里面 + - 加号减号的优先级大于<< >> >>> 左移 右移 无符号右移的优先级，如果要做先右移再减一的操作需要用括号括起来，比如(Integer.MAX_VALUE >> 2) - 1 表示的是max右移两位再减一，如果是Integer.MAX_VALUE >> 2 - 1 表示max右移一位。
2、运算结束后要执行的这句。

if (initialCapacity < 0)   // Too many elements, must back off
               initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements

如果结束后initialCapacity是负数。表示越界了，最后得到的数大于Integer.MAX_VALUE了。就直接把initialCapacity赋值为Integer.MAX_VALUE >> 1。这个时候其实是比user期待的numElements小的，这个时候怎么办呢？其实就交给后面doubleCapacity去处理了。