ArrayDeque.allocateElements（按位操作）

问题描述：

我看的Java 1.6的java.util.ArrayDeque中（队列实现）的源极和偶然在allocateElements（）的执行情况，其大小应该根据给定的数背衬阵列元素：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是什么目的？

答

它看起来像ArrayDeque长度“始终是二的幂”中，为了简化的doubleCapacity()执行，其可以被调用“一个addX()方法之内”。特别是，

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

附录：下面是一个检查在临界值的计算容量只是之前递增到2的下一个较大功率的示例。

/** @see http://*.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

雅得爱Bloch和Lea的注释。 :-) – trashgod 2011-04-03 08:32:32

感谢详细的解答！可耻的是我不知道如何找到最近的2的功率为位操作！ – 2011-04-03 09:11:49

不客气。这是我最喜欢的一个[*位操作黑客*]（https://graphics.stanford.edu/~seander/bithacks.html）。 – trashgod 2016-06-27 09:18:21

答

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

ArrayDeque.allocateElements（按位操作）

相关推荐