Topics / Bit Manipulation / Q17
How do you round up to the next power of two?
Short answer: Subtract one, copy the highest set bit into every lower position with shifts and ORs, then add one. The smearing turns any value into 2ᵏ - 1, and adding one gives 2ᵏ.
uint32_t next_pow2(uint32_t x)
{
x--;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x + 1;
}
Walk-through for x = 37 (0b100101)
x - 1 = 0b100100
|= >>1 = 0b110110
|= >>2 = 0b111111 (already all ones below the top bit)
... = 0b111111 (63)
+ 1 = 0b1000000 (64)
Why subtract one first: so that an exact power of two maps to itself. Without it, next_pow2(64) would give 128.
Edge cases
x = 0→x - 1wraps to0xFFFFFFFF, smearing changes nothing, and+ 1wraps to 0. Decide what 0 should return and handle it explicitly.x > 2³¹→ the answer does not fit in 32 bits and the result wraps to 0.
With CLZ (one instruction on Cortex-M3+):
uint32_t next_pow2_clz(uint32_t x) /* 2 <= x <= 2^31 */
{
return 1u << (32 - __builtin_clz(x - 1));
}
Where it is used: sizing ring buffers and hash tables so you can wrap indices with & (size - 1), choosing a DMA or MPU region size (the classic Arm v7-M MPU requires power-of-two region sizes aligned to their size), and memory allocators that use power-of-two size classes (buddy allocator).