Tại sao kích thước bộ đệm vòng phải là công suất 2?

Question

Tại sao kích thước bộ đệm vòng phải là công suất 2?

Answer 1

Nó phải là sức mạnh của 2 để sử dụng cách tiếp cận được nêu chi tiết bên dưới. Nó không cần phải khác.

Cách tiếp cận chung trông giống như "if (index> = size) {index = size - index;}" (kích thước 10, chỉ mục 10, kết quả là 0). Điều này là chậm hơn và dễ bị lỗi liên quan đến cách tiếp cận sau đây.

Sử dụng một sức mạnh của hai phép chúng tôi tận dụng những điều sau đây:

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

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

Áp dụng mặt nạ này với một Bitwise và, chúng ta có thể cô lập chỉ các bit mà bao gồm các số trong phạm vi 0-31 như chỉ mục tăng:

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) 

Cách tiếp cận này không yêu cầu so sánh, không có nhánh và an toàn (kết quả luôn nằm trong giới hạn). Nó có thêm lợi ích của việc không truy tìm thông tin; trong khi chỉ số 65 giải quyết phần tử 1, tôi vẫn giữ lại thông tin rằng chỉ mục là hợp lý 65 (điều này chứng minh khá hữu ích).

Tôi cũng muốn nói thêm rằng đây là giống như hiệu quả khi chỉ số phát triển đến 3.456.237 (địa chỉ 13 trong bộ đệm) như khi nó 3.

Tôi biết tôi là muộn để đảng, tôi thậm chí không chắc chắn làm thế nào tôi tìm thấy câu hỏi này :-) Hy vọng điều này sẽ giúp.