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

Question

I look through java source code try to learn the implementation of collection. Found a 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 does the following 2 lines mean? Is it a bitwise operation? Why they use it and what's the purpose here?

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

I know one scenario to use the bitwise is to pack 2 values in 1 variable. But it seems this is not the case.

Infallible

Answer 1

Take a look at the initialization code - the Deque is represented as an array whose size is always a power of 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    }

so elements. Length - 1 in binary is basically a series of 1 bits before the size of the array is exceeded.

For instance, if elements is initialized to an array of size 16, then elements.length - 1 is 15, meaning 0..001111 (truncated leading zeros).

So when the head element is reset in pollFirst method (advanced by one), the bitwise & operator is used in order to make the Deque cyclic. Again, if elements is of size 16 and currently head is 15, then head + 1 would be 16, and so:

10000
01111
-----
00000

Meaning, the head is reset to index 0. This allows you to reuse the space you've already allocated, using the array and its O(1) efficiency in inserting and retrieval, without needing to allocate new space.

The same is true for pollLast where you reset the tail variable, i.e. if tail is 0 and elements is of size 16, then:

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

Meaning tail is decremented one value, but moves from 0 to elements.length - 1.

You could have achieved the same with a more "complex" if statement (or by using the trinary operator), however this is a fairly common and acceptable way of implementing a cyclic array.

Oratory

Answer 2

It's a more efficient way of calculating (head+1) % elements.length, which we can do because elements.length is a power of 2. It is more efficient because the mod operator is expensive compared to bitwise and.

On the other end, only using mod for the tail would not work because in Java, -1 % N == -1.

Her