Реализация ArrayDeque.allocateElements (побитовые операции) - PullRequest
Новая
       4

Реализация ArrayDeque.allocateElements (побитовые операции)

5 голосов
/ 03 апреля 2011

Я искал источник Java.Util.ArrayDeque в Java 1.6 (реализация очереди) и наткнулся на 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];
}

Какова цель ORing initialCapacity с самим rshifted?

Ответы [ 2 ]

5 голосов
/ 03 апреля 2011

Похоже, что длина ArrayDeque "всегда является степенью двойки", чтобы упростить реализацию doubleCapacity(), которая может быть вызвана "в методе addX()". В частности, 

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

Добавление: вот пример, который проверяет расчетную емкость при критических значениях за до увеличения до следующей большей степени двух. 

/** @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
1 голос
/ 03 февраля 2016 
    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.

...