</>EmbeddedInterview

How do you round up to the next power of two?

MediumBit Manipulation

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 - 1 wraps to 0xFFFFFFFF, smearing changes nothing, and + 1 wraps 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).