Fast Power-of-Two Ring Buffer Alignment

In high-frequency single-producer single-consumer (SPSC) lock-free ring buffers, converting a 64-bit monotonic sequence number $S$ into a physical buffer index via the integer modulo operator S % C introduces hardware divide latency (up to 20–40 CPU cycles).

When the queue capacity $C$ is strictly constrained to be a power of two ($C = 2^k$), the expensive modulo instruction can be replaced with a single-cycle bitwise AND: $\text{index} = S \;\&\; (C - 1)$

Your Task

1. Implement next_power_of_two(capacity: int) -> int that calculates the smallest power of two greater than or equal to capacity using branchless bitwise operations (for $1 \le capacity \le 2^{62}$).
2. Implement the RingBufferIndexMapper class:
   • __init__(requested_capacity: int): rounds requested_capacity up to the next power of two and initializes the bitmask.
   • get_index(sequence_number: int) -> int: maps sequence number to circular buffer index in $\mathcal{O}(1)$ time.

Constraints

• $1 \le requested\_capacity \le 10^9$
• $0 \le sequence\_number < 2^{63}$

Examples

next_power_of_two(100) # returns 128
next_power_of_two(64)  # returns 64
mapper = RingBufferIndexMapper(100) # capacity 128
mapper.get_index(130)  # returns 130 & 127 = 2