为什么环形缓冲区大小必须是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

我知道我迟到了，我我甚至不知道我是如何找到这个问题的:-)希望这会有所帮助。