¿Por qué un tamaño de búfer de anillo debe tener una potencia de 2?

Question

¿Por qué debe un tamaño de búfer de anillo ser una potencia de 2?

Answer 1

Debe ser una potencia de 2 para utilizar el enfoque que se detalla a continuación. No es necesario que sea de otra manera.

Un enfoque común parece "if (index> = size) {index = size - index;}" (tamaño de 10, índice 10, índice resultante es 0). Esto es más lento y propenso a errores en relación con el siguiente enfoque.

Usando una potencia de dos nos permite tomar ventaja de los siguientes:

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

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

La aplicación de esta máscara con un nivel de bits y, podemos aislar sólo los bits que componen los números en el rango de 0 - 31 como el índice crece:

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) 

Este enfoque requiere ninguna comparación, no hay ramas, y es seguro (índice resultante siempre dentro de ciertos límites). Tiene el beneficio adicional de no destruir la información; mientras que el índice 65 aborda el elemento 1, aún conservo la información de que el índice es lógicamente 65 (lo que resulta bastante útil).

También me gustaría añadir que esto es tan eficiente cuando el índice crece a 3.456.237 (dirección 13 en el búfer) como cuando es 3.

Sé que llego tarde a la fiesta, Ni siquiera estoy seguro de cómo encontré esta pregunta :-) Espero que esto ayude.