ArrayDeque类的addFirst方法

Question

java.util.ArrayDeque类中的addFirst方法的代码是

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

在这里,我无法理解其含义

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

另外,假设数组大小为10. head为0且tail为9(数组已满).在这种情况下,什么索引系统会插入？(我的理解是:如果数组已满,则首先增加其大小,然后在arraySize() - 1索引中插入.)

Answer 1

以下行的功能基本上是(head - 1) MODULO (elements.length)这样,因此从head减去1会导致最大可能值而不是-1 head == 0.

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

10是无效长度elements,根据实现,elements.length总是两个幂.如果不是这种情况,则操作无效.

了解其工作原理需要了解位操作.假设elements.length == 16 == 00010000b并且为了简单起见,值的长度是8位而不是实际的32位:

(elements.length - 1)用于得到n位长的位掩码,其中2 ^ n是元素的当前长度.(elements.length - 1) == 15 == 00001111b在这种情况下.

如果head > 0和head < elements.length(这是给定的)那么(head - 1) & (elements.length - 1) == (head - 1),因为与1s的ANDing什么都不做.

如果head == 0,head - 1 == -1 == 11111111b.(二进制补码有符号整数表示法,尽管您也可以将其视为一个简单的整数溢出.)使用掩码进行AND运算(head - 1) & 00001111b == 11111111b & 00001111b == 00001111b == 15,这是所需的值.