Write code in C to "round up" any number to the next "power of 2", unless the number is already a power of 2. For example, 5 rounds up to 8, 42 rounds up to 64, 128 rounds to 128. When is this algorithm useful?

The classic bit-smear technique: decrement, propagate (OR) the highest set bit down into every lower bit position to form a contiguous run of 1s, then add 1 to carry up to the next power of two. The initial n-- handles the "already a power of two stays the same" requirement.

#include <stdint.h>

uint32_t round_up_pow2(uint32_t n) {
    if (n == 0u) {
        return 1u;     /* define 0 -> 1; smear alone would yield 0 */
    }
    n--;               /* so exact powers of two are unchanged */
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;               /* carry to the next power of two */
    return n;
}

How it works on n = 42 (0b101010): n-- → 41 = 0b101001; after the OR-shifts every bit below the MSB fills in → 0b111111 = 63; n++ → 64. For n = 128 (already a power of two): n-- → 127 = 0b1111111, smear leaves it 127, n++ → 128 (unchanged, as required).

Notes / variants:

• Handle n == 0 explicitly — the smear of 0 is 0, then +1 gives 1; pick the convention you want (1 is typical).
• For 64-bit inputs, add one more step: n |= n >> 32;.
• CLZ-based alternative (single instruction on capable cores), valid for n > 1:
  c

  Copy

  uint32_t round_up_pow2_clz(uint32_t n) {
      if (n <= 1u) return 1u;
      return 1u << (32 - clz32(n - 1));   /* clz32 from the CLZ answer */
  }

  Using n - 1 makes exact powers of two map to themselves.

Where it's useful:

• Memory allocators / buddy allocators / size classes — rounding requests up to power-of-two blocks.
• Hash tables and ring/circular buffers — power-of-two capacity lets you replace % size with a fast & (size - 1) mask.
• GPU textures / DMA / alignment — hardware that requires power-of-two dimensions or alignment.
• Geometric growth of dynamic arrays/vectors.