Зачем нужен размер кольцевого буфера, равный 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.

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