Perché una dimensione del buffer circolare deve essere pari a 2?

Question

Perché una dimensione del buffer dell'anello deve essere pari a 2?

Answer 1

Deve essere una potenza di 2 per utilizzare l'approccio descritto di seguito. Non è necessario essere diversamente.

Un approccio comune è simile a "if (index> = size) {index = size - index;}" (dimensione di 10, indice 10, indice risultante è 0). Questo è più lento e soggetto a errori relativi al seguente approccio.

Utilizzando una potenza di due ci permette di sfruttare la seguente:

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

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

Applicando questa maschera con un bit per bit e, possiamo isolare solo i bit che compongono i numeri nell'intervallo 0 - 31 come l'indice cresce:

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) 

Questo approccio non richiede il confronto, senza rami, ed è sicuro (con conseguente indice di sempre entro certi limiti). Ha il vantaggio di non cedere informazioni; mentre l'indice 65 si rivolge all'elemento 1, conservo ancora l'informazione che l'indice è logicamente 65 (il che si rivela abbastanza utile).

Vorrei anche aggiungere che questo è altrettanto efficace quando l'indice cresce fino a 3.456.237 (indirizzo 13 nel buffer), come quando si tratta di 3.

So di essere in ritardo alla festa, mi Non sono nemmeno sicuro di come ho trovato questa domanda :-) Spero che questo aiuti.