What purpose is the '&' symbol used for variable assignment in some java libraries?-CodePudding

I don't understand what the & operator is used for in the pollFirst method of the ArrayDeque class.

public E pollFirst() {
    int h = this.head;
    E result = this.elements[h];
    if (result == null) {
        return null;
    } else {
        this.elements[h] = null;
        this.head = h   1 & this.elements.length - 1;
        return result;
    }
}

What is intended with the & operator in this piece of code?

this.head = h   1 & this.elements.length - 1;

CodePudding user response：

The & is the bitwise AND operator.

Elsewhere in the ArrayDeque source code (for that version!), it states that the size of elements is always a power of 2. Thus:

    this.head = h   1 & this.elements.length - 1;

is computing a new head value as h 1 modulo the size of the elements array.

Why did they do it that way? Possibly a micro-optimization.

Note that from Java 9 onwards, the method is written as:

public E pollFirst() {
    final Object[] es;
    final int h;
    E e = elementAt(es = elements, h = head);
    if (e != null) {
        es[h] = null;
        head = inc(h, es.length);
    }
    return e;
}

and inc doesn't assume that es.length is a power of 2.

CodePudding user response：

The ArrayDeque in Java provides a way to apply resizable-array in addition to the implementation of the Deque interface. It is also known as Array Double Ended Queue or Array Deck. This is a special kind of array that grows and allows users to add or remove an element from both sides of the queue.

please visit this link for more information about ArrayDeque.

& operator is called bitwise and operator.

This operator is a binary operator, denoted by ‘&.’ It returns bit by bit AND of input values, i.e., if both bits are 1, it gives 1, else it shows 0.

a = 5 = 0101 (In Binary)
b = 7 = 0111 (In Binary)

Bitwise AND Operation of 5 and 7
  0101
& 0111
 ________
  0101  = 5 (In decimal)

This bitwise and example from GFG .

Correct implementation of `pollFirst` for ArrayDeque;

public E pollFirst() {
    int h = this.head;
    E result = this.elements[h];
    if (result == null) {
        return null;
    } else {
        this.elements[h] = null;
        this.head = (h   1) & (this.elements.length - 1);
        return result;
    }
}

After removing element head will be incemented to next index if the length is equal to the head then head should be made 0.

Without using & operator we can also implement the pollFirst method:

public E pollFirst() {
    int h = this.head;
    E result = this.elements[h];
    if (result == null) {
        return null;
    } else {
        this.elements[h] = null;
        this.head = ((h 1) >= this.elements.length) ? 0 : (h 1);//if head  1 is greater then or equal the number of elements then make head as 0 other wise increment head by 1
        return result;
    }
}

Correct implementation of pollFirst for ArrayDeque;

Correct implementation of `pollFirst` for ArrayDeque;