7

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 索引中插入。）

4

2 回答 2

16

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

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

10 不是 的有效长度elements，根据实现，elements.length始终是 2 的幂。如果不是这种情况，则该操作将不起作用。

理解为什么会这样工作需要了解位操作。为简单起见，假设elements.length == 16 == 00010000b值的长度是 8 位而不是实际的 32 位：

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

如果head > 0and head < elements.length（这是给定的），那么(head - 1) & (elements.length - 1) == (head - 1), 因为与 1 进行 ANDing 什么都不做。

如果head == 0，head - 1 == -1 == 11111111b。（二进制补码有符号整数表示法，尽管您也可以将其视为简单的整数溢出。）与掩码进行与运算(head - 1) & 00001111b == 11111111b & 00001111b == 00001111b == 15，这是想要的值。

于 2015-02-04T06:58:39.937 回答
0

这里它的 using&运算符意味着它将在两个整数中执行二进制与运算。

让我们假设您的案例 head = 0 那么 head 将变为

头 = -1

和elements.length = 16（默认情况下，也正如@Adrian所说，它只有2的幂）

因此执行操作-1 & 15（即 11111111 和 00001111）它将变为 15，这是添加元素的目标位置。

于 2015-02-04T07:13:59.157 回答