爲什麼環形緩衝區大小必須是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

我知道我遲到了，我我甚至不知道我是如何找到這個問題的:-)希望這會有所幫助。