リングバッファサイズを2の累乗にする必要があるのはなぜですか？

Question

なぜリングバッファサイズは2の累乗でなければならないのですか？

Answer 1

下記の方法を使用するには、2の累乗でなければなりません。それは別のものである必要はありません。

一般的なアプローチは、「if（index> = size）{index = size-index;}」（サイズ10、インデックス10、結果インデックスが0）のように見えます。これは、次のアプローチと比較して遅くなり、エラーになりやすい。 - 31として

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

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

ビット単位でこのマスクを適用すると、我々は0の範囲内の数字を構成するビットのみを分離することができます：2の電源を使用して

は

私たちは、次の利点を取ることができますインデックスが育つ：

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であるという情報を保持しています（これは非常に便利です）。

私も、私は、これはそれが3

だとき、私はパーティーに遅刻知っているようにインデックスが3456237（バッファ内のアドレス13）に成長したときに同じように効率的であることを追加したいですどのように私はこの質問を発見したかわからない:-)これは助けて欲しい。