Why must a ring buffer size be a power of 2?

Question

Why must a ring buffer size be a power of 2?

Answer 1

It must be a power of 2 to use the approach detailed below. It need not be otherwise.

A common approach looks like "if (index >= size) { index = size - index; }" (size of 10, index 10, resulting index is 0). This is slower and prone to error relative to the following approach.

Using a power of two allows us to take advantage of the following:

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

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

Applying this mask with a bitwise and, we can isolate only the bits that comprise numbers in the range of 0 - 31 as the index grows:

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)

This approach requires no comparisons, no branches, and is safe (resulting index always within bounds). It has the added benefit of not trashing information; while index 65 addresses element 1, I still retain the information that the index is logically 65 (which proves quite useful).

I'd also like to add that this is just as efficient when the index grows to 3456237 (address 13 in the buffer) as when it's 3.

I know I'm late to the party, I'm not even sure how I found this question :-) Hope this helps.