Dlaczego rozmiar bufora pierścieniowego musi wynosić 2?

Question

Dlaczego rozmiar bufora pierścieniowego musi wynosić 2?

Answer 1

To musi być potęga 2, aby użyć podejścia opisanego poniżej. Nie musi być inaczej.

Typowe podejście wygląda tak: "if (index> = size) {index = size - index;}" (rozmiar 10, indeks 10, wynikowy indeks to 0). Jest to wolniejsze i bardziej podatne na błędy w stosunku do następującego podejścia.

Stosując moc dwóch pozwala nam skorzystać z następujących czynności:

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

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

Stosując tę ​​maskę z bitowe i możemy wyizolować tylko bity, które zawierają numery w zakresie od 0 - 31, jak indeks rośnie:

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) 

Takie podejście nie wymaga żadnych porównań, gałęzie, i jest bezpieczny (wynikające indeks zawsze w granicach). Dodatkową zaletą jest to, że nie powoduje utraty informacji; podczas gdy indeks 65 odnosi się do elementu 1, nadal zachowuję informację, że indeks jest logicznie 65 (co jest całkiem przydatne).

Chciałbym również dodać, że to jest tak samo skuteczny, gdy indeks rośnie do 3456237 (adres 13 w buforze), a kiedy nadszedł 3.

Wiem, że późno do partii, ja nie jestem nawet pewien, jak znalazłem to pytanie :-) Mam nadzieję, że to pomaga.