配列操作におけるビット演算と通常演算の混同（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(); 
} 

基本的には、ヘッドの値が1つ減少した後、ビット単位elements.lengthマイナス1で「AND演算」されます。この操作は、配列のどのインデックスが新しい値eを保持するかを決定し、配列の先頭に循環ラップを戻します。 OKこれまで（私は間違っていないと思います）。

しかし、その後、私たちはラインに来る：

if (head == tail) doubleCapacity(); 

頭と尾はint型です。たとえビットが "anded"（配列がいっぱいで展開しなければならないことを意味する）の後、配列内の同じ位置に等しくても、それらはintと同じになりません（これはテストされているものですか？

だから私はこの仕組みが見えない。

誰でも手助けできますか？

私は配列のインデックスを参照しています。要素のインデックスは参照していません。

head

Answer 1

とtail最初に配列の最初のインデックスを参照する - 補助配列の0

初期の長さは、デフォルトでは16であり、常に2の累乗です。これは、引用したコードのスニペットにとって重要です。

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

ここで、キューの最後に15個の要素を追加するとします。この時点で

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

は、15のを除いて、配列のすべてのインデックスが占有されている：15追加した後、あなたが得るように、あなたが最後に要素を追加するたびに、tailインデックスは、インクリメントされます。

今、私たちはあなたが引用されたコードを取得：あなたはaddFirstを呼び出すと

、headは、（必要であれば、配列の末尾にラップアラウンド）をデクリメントしなければならない、そして新しい要素をインデックスに追加されます新しい値head。

がheadので0、head、(head - 1) & (elements.length - 1)の新たな値であった、-1 & 15であるか、または15、配列の最後のインデックスに等しい11111111111111111111111111111111 & 00000000000000000000000000001111、（バイナリに変換します）。

この時点で、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の累乗であるためにのみ当てはまります。