Почему размер кольцевого буфера должен быть степенью 2?

Question

Почему размер кольцевого буфера должен быть степенью 2?

Answer 1

Это должно быть степень 2, чтобы использовать подход, описанный ниже. Это не должно быть иначе.

Общий подход выглядит так: "if (index >= size) { index = size - index; }" (размер 10, индекс 10, результирующий индекс равен 0). Это медленнее и подвержено ошибкам по сравнению со следующим подходом.

Использование степени двойки позволяет нам воспользоваться следующими преимуществами:

size = 32
bin(size) => '00100000'

mask = size - 1;
bin(mask) => '00011111'

Применяя эту маску с побитовым и, мы можем изолировать только биты, которые содержат числа в диапазоне от 0 до 31, по мере роста индекса:

index = 4
bin(4 & mask) => '00000100' (4)

# index 32 wraps.  note here that we do no bounds checking, 
# no manipulation of the index is necessary.  we can simply 
# and safely use the result.
index = 32
bin(index & mask) => '00000000' (0)

index = 33
bin(index & mask) => '00000001' (1)

index = 64
bin(index & mask) => '00000000' (0)

index = 65
bin(index & mask) => '00000001' (1)

Этот подход не требует никаких сравнений, ветвей и является безопасным (результирующий индекс всегда в пределах границ). Это имеет дополнительное преимущество: не уничтожать информацию; в то время как индекс 65 обращается к элементу 1, я все еще сохраняю информацию о том, что индекс логически равен 65 (что оказывается весьма полезным).

Я также хотел бы добавить, что это так же эффективно, когда индекс увеличивается до 3456237 (адрес 13 в буфере), как когда он равен 3.

Я знаю, что опоздал на вечеринку, я даже не уверен, как я нашел этот вопрос:-) Надеюсь, это поможет.