java - 在数组操作中混合按位和普通操作(java)

Question

以下代码来自标准java库中的ArrayDeque。我选择它有点随意，因为整个代码中有很多这个想法的例子。

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

基本上，正如我所读，head 的值减一，然后与 elements.length 减一按位“与”。此操作确定数组的哪个索引将保存新值 e，并允许循环回绕到数组的开头。到目前为止还不错(我希望没有错)。

但是接下来我们就到了这一行:

if (head == tail) doubleCapacity();

头和尾都是整数。即使它们在按位“与”后等于数组中的相同位置(意味着数组已满并且需要扩展)，也不会使它们等于整数(这就是正在测试的，对吧？)。

所以...我不明白这是如何工作的。

有人可以帮忙吗？

经过编辑以澄清我指的是数组的索引，而不是它的任何元素。

Answer 1

head 和 tail 最初引用数组的第一个索引 - 0。

默认情况下，后备数组的初始长度为 16，并且始终为 2 的幂。这对于您引用的代码片段的工作非常重要。

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^
head
tail

现在假设您将 15 个元素添加到队列末尾。每次向末尾添加元素时，tail 索引都会递增，因此添加 15 次后，您将得到:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^                                  ^
head                               tail

此时，数组中除了15之外的所有索引都已被占用。

现在我们来看看您引用的代码:

当你调用addFirst时，head应该递减(如果需要的话，环绕到数组的末尾)，并且新元素被添加到数组的索引处。 head 的新值。

由于 head 为 0，head 的新值 (head - 1) & (elements.length - 1) 为-1 & 15 或(转换为二进制)11111111111111111111111111111111 & 00000000000000000000000000001111，等于 15，即数组的最后一个索引。

此时，head 和 tail 都包含数组的最后一个索引 - 15。

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
                                   ^
                                   head
                                   tail

这意味着数组已满，必须加倍。

这里需要注意的重要一点是 (head - 1) & (elements.length - 1) 相当于 (head - 1) % elements.length 。这是正确的，因为 elements.length 是 2 的幂。