Implementación de ArrayDeque.allocateElements (operaciones bit a bit)

Question

Estaba viendo el origen de Java.Util.ArrayDeque de Java 1.6 (una implementación de cola) y tropecé con allocateElements() que debería dimensionar la matriz de respaldo de acuerdo con el número dado de elementos:

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

¿Cuál es el propósito de ORing initialCapacity con rhifted?

Answer 1

Parece que la longitud ArrayDeque "es siempre una potencia de dos" con el fin de simplificar la implementación de doubleCapacity(), que puede ser invocada "dentro de un método addX()." En particular,

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

Adición: He aquí un ejemplo que examina la capacidad calculada a valores críticos simplemente antes incrementando a la siguiente potencia mayor de dos.

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

Consola:

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

es igual a:

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) 

esta forma se establece todos los bits más baja que el primero 1.