你爲什麼要用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; 

但掩蓋它只是一個速度（而不是可讀性）的改進。