爲什麼ArrayDeque類在pollFirst方法中使用按位操作？

我看看通過java源代碼試着學習集合的實現。在ArrayDeque類中找到了一件有趣的事情。爲什麼ArrayDeque類在pollFirst方法中使用按位操作？

public E pollFirst() { 
    int h = head; 
    @SuppressWarnings("unchecked") 
    E result = (E) elements[h]; 
    // Element is null if deque empty 
    if (result == null) 
     return null; 
    elements[h] = null;  // Must null out slot 
    head = (h + 1) & (elements.length - 1); 
    return result; 
} 

public E pollLast() { 
    int t = (tail - 1) & (elements.length - 1); 
    @SuppressWarnings("unchecked") 
    E result = (E) elements[t]; 
    if (result == null) 
     return null; 
    elements[t] = null; 
    tail = t; 
    return result; 
}

以下兩行代表什麼意思？這是一個按位操作嗎？他們爲什麼使用它，這裏的目的是什麼？

head = (h + 1) & (elements.length - 1); 
    int t = (tail - 1) & (elements.length - 1);

我知道使用按位的一種情況是將2個值打包在1個變量中。但似乎並非如此。

來源

2016-04-24 Albert Gao

看一看初始化代碼 - 的雙端隊列爲表示爲一個數組，其大小總是2的冪：

195 public ArrayDeque(int numElements) { 
196  allocateElements(numElements); 
197 } 

124 private void allocateElements(int numElements) { 
125  int initialCapacity = MIN_INITIAL_CAPACITY; 
126  // Find the best power of two to hold elements. 
127  // Tests "<=" because arrays aren't kept full. 
128  if (numElements >= initialCapacity) { 
129   initialCapacity = numElements; 
130   initialCapacity |= (initialCapacity >>> 1); 
131   initialCapacity |= (initialCapacity >>> 2); 
132   initialCapacity |= (initialCapacity >>> 4); 
133   initialCapacity |= (initialCapacity >>> 8); 
134   initialCapacity |= (initialCapacity >>> 16); 
135   initialCapacity++; 
136 
137   if (initialCapacity < 0) // Too many elements, must back off 
138    initialCapacity >>>= 1;// Good luck allocating 2^30 elements 
139  } 
140  elements = (E[]) new Object[initialCapacity]; 
141 }

所以elements.length - 1是二進制基本上的尺寸之前的一系列1位數組已超出。

例如，如果elements初始化爲大小爲16的陣列，然後是elements.length - 1 15，這意味着0..001111（截斷前導零）。

因此，當pollFirst方法中的head元素被重置時（由1提前），使用按位&運算符來使Deque循環。同樣，如果elements是大小16，目前head是15，那麼head + 1是16，所以：

意思，head重置爲索引0這樣就可以重新使用，您對空間已經分配，使用數組及其O（1）插入和檢索效率，而不需要分配新的空間。其中重置tail變量，即，如果tail是0和elements是大小爲16，則

這同樣適用於pollLast真：

tail  00000 
tail-1 11111 (-1 in two's complement) 
      01111 
      ----- 
      01111

含義tail遞減一個值，但移動從0到elements.length - 1。

你可以用一個更復雜的if語句（或使用trinary操作符）實現相同的操作，但這是實現循環數組的一個相當常見和可接受的方法。

來源

2016-04-24 15:48:17

它的計算(head+1) % elements.length，這是我們可以做的，因爲elements.length是2的冪更有效，因爲國防部運營商相比，按位和是昂貴的更有效的方式。

另一方面，僅使用mod對於tail不起作用，因爲在Java中，-1 % N == -1。

來源

2016-05-22 00:08:10 EthanP

爲什麼ArrayDeque類在pollFirst方法中使用按位操作？

回答

相關問題