为什么环形缓冲区大小必须是2的幂？

Question

为什么环形缓冲区大小必须是2的幂？

Answer 1

使用下面详述的方法必须是2的幂.它不一定是其他的.

常见的方法看起来像"if(index> = size){index = size - index;}"(大小为10,索引10,结果索引为0).相对于以下方法,这较慢且容易出错.

使用2的幂允许我们利用以下内容:

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

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

以bitwise方式应用此掩码,当索引增长时,我们只能隔离包含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那样有效.

我知道我迟到了,我甚至不确定我是怎么发现这个问题的:-)希望这会有所帮助.