AddFirst class method ArrayDeque

Question

AddFirst method code in java.util.ArrayDeque class

public void addFirst(E e) { if (e == null) throw new NullPointerException(); elements[head = (head - 1) & (elements.length - 1)] = e; if (head == tail) doubleCapacity(); } 

Here I can not understand the meaning

 head = (head - 1) & (elements.length - 1) 

Also, suppose the size of the array is 10. head is at 0 and the tail is at 9 (the array is full). In this case, in which index system will the insertion be performed? (I understand: if the array is full, first increase its size, and then enter arraySize () - 1 in the index).

Answer 1

The functionality of the next line is basically (head - 1) MODULO (elements.length) , so subtracting 1 from the head leads to the maximum possible value instead of -1 when head == 0 .

 head = (head - 1) & (elements.length - 1) 

10 does not correspond to the length of elements , according to the implementation of elements.length always has a force of two. If this is not the case, the operation will not work.

Understanding why this works requires knowledge of bit operations. Assuming elements.length == 16 == 00010000b and that for simplicity values ​​is 8 bits instead of the actual 32:

(elements.length - 1) used to get a bit mask with a length of n bits, where 2 ^ n is the current length of the elements. (elements.length - 1) == 15 == 00001111b in this case.

If head > 0 and head < elements.length (which is given), then (head - 1) & (elements.length - 1) == (head - 1) , since ANDing does nothing with 1s.

If head == 0 , head - 1 == -1 == 11111111b . (An integer designation with two additions, although you can also think of it as a simple integer overflow.) ANDing with a mask (head - 1) & 00001111b == 11111111b & 00001111b == 00001111b == 15 , which is the required value.

Answer 2

Here, his use of the & operator means that he will perform the binary AND operation as in integers.

lets assume your case head = 0, then the head will become

head = -1

and elements.length = 16 (by default, as well as @Adrian says it will only have 2)

therefore, performing operation -1 & 15 (i.e. 11111111 and 00001111), it will become 15, which is the target position for adding the item.