Geek Answers Handbook

Why does the ArrayDeque class use a bitwise operation in the pollFirst method?

I am browsing the java source code trying to learn the collection implementation. Found an interesting thing in the ArrayDeque class.

public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result == null)
        return null;
    elements[h] = null;     // Must null out slot
    head = (h + 1) & (elements.length - 1);
    return result;
}

public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];
    if (result == null)
        return null;
    elements[t] = null;
    tail = t;
    return result;
}

What do the following two lines mean? Is this a bitwise operation? Why are they using it and what is the purpose here?

    head = (h + 1) & (elements.length - 1);
    int t = (tail - 1) & (elements.length - 1);

I know that one scenario for using bitwise is to pack 2 values ​​into 1 variable. But this does not seem to be the case.

+4
source share
2 answers

Take a look at the initialization code - Deque is represented as an array whose size is always 2:

195    public ArrayDeque(int numElements) {
196        allocateElements(numElements);
197    }

124    private void allocateElements(int numElements) {
125        int initialCapacity = MIN_INITIAL_CAPACITY;
126        // Find the best power of two to hold elements.
127        // Tests "<=" because arrays aren't kept full.
128        if (numElements >= initialCapacity) {
129            initialCapacity = numElements;
130            initialCapacity |= (initialCapacity >>>  1);
131            initialCapacity |= (initialCapacity >>>  2);
132            initialCapacity |= (initialCapacity >>>  4);
133            initialCapacity |= (initialCapacity >>>  8);
134            initialCapacity |= (initialCapacity >>> 16);
135            initialCapacity++;
136
137            if (initialCapacity < 0)   // Too many elements, must back off
138                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
139        }
140        elements = (E[]) new Object[initialCapacity];
141    }

elements.length - 1 , 1 , .

, elements 16, elements.length - 1 15, 0..001111 ( ).

, head reset pollFirst ( ), & , Deque. , elements 16, head 15, head + 1 16, :

10000
01111
-----
00000

head reset 0. , , O (1) , .

pollLast, reset tail, .. tail 0 elements 16, :

tail      00000
tail-1    11111   (-1 in two complement)
          01111
          -----
          01111

tail , 0 elements.length - 1.

"" if ( trinary), .

+6

(head+1) % elements.length, , elements.length 2. , mod .

, mod tail , Java, -1 % N == -1.

0

More articles:


All Articles