Метод 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, а tail равен 9(массив заполнен). В этом случае по какой системе индекса будет выполняться вставка? (Насколько я понимаю: если массив заполнен, то сначала увеличьте его размер, а затем вставьте в индекс arraySize()-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) используется для получения битовой маски длиной n битов, где 2^n - текущая длина элементов. (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

Здесь его использование & Оператор означает, что он будет выполнять двоичные операции И в обоих целых числах.

давайте предположим, что ваш случай head = 0, тогда голова станет

голова = -1

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

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