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

使用按位和应用此掩码，随着索引的增长，我们可以仅隔离包含 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 时一样有效。

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