FULL PRODUCT VERSION :
java version "1.6.0_45"
Java(TM) SE Runtime Environment (build 1.6.0_45-b06)
Java HotSpot(TM) Client VM (build 20.45-b01, mixed mode, sharing)

ADDITIONAL OS VERSION INFORMATION :
All OS

A DESCRIPTION OF THE PROBLEM :
The problem is on the method allocateElements.
When the paramenter is a number power of 2 (8, 16, 32, etc.) the calculated capacity is the double (16, 32, 64, etc.).
The problem is on the strategy to add the bits at the rigth, because the bits are allays added even the passed argument have a valid size (number power 2).
One way to resolve, is:
1 - on the if convert "<=" on "<", this will solve the problem for minimum capacity (8);
2 - initially inside the if, assign the passed argument -1 to the initialCapacity variable: "initialCapacity = numElements - 1;" ; (this will make the algoritm start on the previous number that wil be anulated by "initialCapacity++;" at the end;

problematic method with my annotations:

    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) { // change to: if (numElements = initialCapacity) {
            initialCapacity = numElements; // change to: initialCapacity = numElements - 1;
            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];
    }


STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
unit test code:

    @Test
    public void testArrayDequeAllocateElements() throws Exception {
        Object[] elementsArr = getelementsArrFromArrayDeque(new ArrayDeque<String>(8));
        assertEquals(8, getelementsArrFromArrayDeque(new ArrayDeque<String>(8)).length);// faill
        assertEquals(16, getelementsArrFromArrayDeque(new ArrayDeque<String>(9)).length);
        assertEquals(16, getelementsArrFromArrayDeque(new ArrayDeque<String>(10)).length);
        assertEquals(16, getelementsArrFromArrayDeque(new ArrayDeque<String>(11)).length);
        assertEquals(16, getelementsArrFromArrayDeque(new ArrayDeque<String>(12)).length);
        assertEquals(16, getelementsArrFromArrayDeque(new ArrayDeque<String>(13)).length);
        assertEquals(16, getelementsArrFromArrayDeque(new ArrayDeque<String>(14)).length);
        assertEquals(16, getelementsArrFromArrayDeque(new ArrayDeque<String>(15)).length);
        assertEquals(16, getelementsArrFromArrayDeque(new ArrayDeque<String>(16)).length);// faill
        assertEquals(32, getelementsArrFromArrayDeque(new ArrayDeque<String>(17)).length);
    }

    private Object[] getelementsArrFromArrayDeque(ArrayDeque<String> ad) throws NoSuchFieldException, IllegalAccessException {
        Object[] elementsArr = new Object[0];
        Field elementsField = ArrayDeque.class.getDeclaredField("elements");
        elementsField.setAccessible(true);
        elementsArr = (Object[]) elementsField.get(ad);
        return elementsArr;
    }


EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The capacity should be the passed argument (if power of 2) ou the next power of 2 value
ACTUAL -
when power of 2 value passed (8, 16, 32, etc.) the capacity is the the double (16, 32, 64, etc.)

REPRODUCIBILITY :
This bug can be reproduced always.