AddFirst метод ArrayDeque класса

Question

Шифр ​​метода AddFirst в классе java.util.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 = (head - 1) & (elements.length - 1) 

Предположим также, если размер массива равен 10. head находится в 0, а хвост - в 9 (массив заполнен). В этом случае, в какой индексной системе будет выполняться вставка? (Мое понимание: если массив заполнен, сначала увеличьте его размер, а затем вставьте в индекс массива() - 1.)

Answer 1

Функцией следующей строки является в основном (head - 1) MODULO (elements.length), так что вычитание 1 из головы приводит к максимальному возможному значению вместо -1 при head == 0.

head = (head - 1) & (elements.length - 1) 

10 не действует длина elements, в соответствии с реализацией, elements.length всегда является степенью двойки. Если бы это было не так, операция не сработала.

Понимание того, почему это работает, требует знания бит-операций. Предполагая elements.length == 16 == 00010000b и что длина значений 8 бит вместо фактического 32 для простоты:

(elements.length - 1) используются для получения битовой маски единиц п битых длинной, где-^ п является текущей длиной элементов. (elements.length - 1) == 15 == 00001111b в этом случае.

Если head > 0 и head < elements.length (что является данным), то (head - 1) & (elements.length - 1) == (head - 1), так как ANDing с 1s ничего не делает.

Если head == 0, head - 1 == -1 == 11111111b. (Обозначение целого числа с двумя символами дополнено, хотя вы также можете рассматривать его как простое переполнение целого числа.) ANDing с маской (head - 1) & 00001111b == 11111111b & 00001111b == 00001111b == 15, которая является требуемым значением.

Answer 2

Здесь его использование оператором & означает, что он выполняет двоичную операцию AND как в целых числах.

позволяет предполагать ваш случай голова = 0, то голова будет

голова = -1

и elements.length = 16 (который по умолчанию, а также как @Adrian сказал, что это будет только власть из 2)

поэтому выполнение операции -1 & 15 (т.е. 11111111 & 00001111) станет 15, который является целью для добавления элемента.