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

ORC initialCapacity與自己的rshifted是什麼目的？

Answer 1

它看起來像ArrayDeque長度「始終是二的冪」中，爲了簡化的doubleCapacity()執行，其可以被調用「一個addX()方法之內」。特別是，

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