你为什么要用i =（i + 1）＆mask来递增，mask是0b1111？

Question

我一直在寻找的ArrayDeque.contains(Object o)的源代码时，我发现这个实现：

/** 
* Returns {@code true} if this deque contains the specified element. 
* More formally, returns {@code true} if and only if this deque contains 
* at least one element {@code e} such that {@code o.equals(e)}. 
* 
* @param o object to be checked for containment in this deque 
* @return {@code true} if this deque contains the specified element 
*/ 
public boolean contains(Object o) { 
    if (o == null) 
     return false; 
    int mask = elements.length - 1; 
    int i = head; 
    Object x; 
    while ((x = elements[i]) != null) { 
     if (o.equals(x)) 
      return true; 
     i = (i + 1) & mask; 
    } 
    return false; 
} 

这里，数组的大小是2的指数，所以mask应与全1的二进制数。在我看来，i = (i + 1) & mask与i = i + 1完全相同。有谁能告诉我为什么这样实施？

Answer 1

该行适用模数有限递增操作的快速版本。

i = (i + 1) & (length - 1); 

对于长度8你

0 -> 1 
1 -> 2 
2 -> 3 
3 -> 4 
4 -> 5 
5 -> 6 
6 -> 7 
7 -> 0 

您从时钟（近，因为我们usally与1而不是0开始时钟），

有一个约束知道类似的行为，长度必须能写成2^n，2,4,8,16,32,64,128,256,512,1024，...

它的工作原理是因为（2^n）-1的位表示是有n个的面具。 例如（2^5）-1是二进制0b00011111。

任何数字0 < = x < 2^n将不加改变地传递掩码（2^n）-1。当应用掩码时，数字2^n将被设置为0。

更一般的方法是使用modulo％。但模数通常比比特操作慢得多，比如“和”（&）

Answer 2

我不熟悉实现，但看起来像一个“循环数组”。 head是第一个元素的索引，并通过递增和屏蔽边界周围的迭代循环。

数组中的“最后一个”槽始终为空（== null），如果找不到对象，将会结束迭代，并返回false。

Answer 3

这样做是为了包裹柜台。正如你已经说了，如果要素的数量是2的幂，所以elements.length -1将是所有位1.

mask = 7 // we assume a elements.length of 8 
x = (x + 1) & mask // will be 7 and 7, so result is 7 

现在我们又增加

x = (x + 1) & mask // now it is 8 and 7, so result will be zero 

其他，也许更具有可读性，接近于达到相同的结果将是：

if (x < elements.length) x=x+1 else x=0; 

x = x < elements.length ? x+1 : 0; 

x = (x + 1) % elements.length; 

但掩盖它只是一个速度（而不是可读性）的改进。