Powers of two and alignment

Overview

Two related rounding problems show up constantly in systems code. Rounding up to a power of two takes 1000 to 1024 — used to size hash tables and buffers so later arithmetic can use masks instead of division. Aligning up takes an address or offset to the next multiple of some alignment — used because CPUs, allocators and DMA engines require addresses to sit on 4-, 8- or 16-byte boundaries. Both have elegant bit solutions: bit-smearing fills every position below the highest set bit so a +1 carries into a clean power of two, and (x + a - 1) & ~(a - 1) rounds up to any power-of-two alignment.

Why it matters

Alignment is a correctness requirement, not a nicety — a misaligned access is a performance penalty on x86 and a hard fault on many ARM and embedded targets. And power-of-two sizing is what allows hash % n to become hash & (n - 1), a change that shows up directly in the throughput of hash tables and ring buffers. Both formulas are short enough to write from memory and subtle enough to get wrong.

Core concepts

Bit smearing. Starting from x - 1, the sequence x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; propagates the highest set bit downward until every lower position is 1. Adding 1 then carries all the way up, producing the next power of two. The doubling shift counts (1, 2, 4, 8, 16) cover all 32 positions in five steps.

Why x-- first. Decrementing before smearing makes the function idempotent: an input that is already a power of two is returned unchanged rather than doubled. round_up_pow2(1024) must be 1024, not 2048.

Aligning up. For a power-of-two alignment a, a - 1 is a mask of the low bits. (x + a - 1) pushes the value past the boundary; & ~(a - 1) clears the low bits, landing exactly on the next multiple. align_up(13, 8) → 16; align_up(16, 8) → 16.

The power-of-two precondition. The alignment formula is only valid when a is a power of two, because only then is a - 1 a clean low-bit mask. Assert it.

Overflow. x + a - 1 can wrap for values near the top of the range; check before adding when the input is untrusted.

Syntax notes

unsigned round_up_pow2(unsigned x) {
    if (x <= 1) return 1u;      // 0 and 1 both round to 1
    x--;                        // makes exact powers of two idempotent
    x |= x >> 1;  x |= x >> 2;  x |= x >> 4;
    x |= x >> 8;  x |= x >> 16; // smear the top bit down over 32 positions
    return x + 1u;
}

/* a MUST be a power of two */
unsigned align_up(unsigned x, unsigned a) {
    return (x + (a - 1u)) & ~(a - 1u);
}

Key points:

• The shift sequence 1,2,4,8,16 covers 32 bits; a 64-bit version needs a final x |= x >> 32.
• x-- before smearing is what keeps exact powers of two unchanged.
• align_up silently misbehaves for a non-power-of-two a — assert the precondition.

Lesson

Two rounding tricks: round up to a power of two by smearing the highest set bit downward (x--; x|=x>>1; ...; x++), and align up to a power-of-two boundary with (x + a-1) & ~(a-1). Both are O(1) and branch-free.

The demo rounds several sizes and aligns to a page.

Code examples

#include <stdio.h>
static unsigned round_up_pow2(unsigned x){ if(x<=1) return 1u; x--; x|=x>>1; x|=x>>2; x|=x>>4; x|=x>>8; x|=x>>16; return x+1u; }
static unsigned align_up(unsigned x,unsigned a){ return (x + (a-1u)) & ~(a-1u); }
int main(void){
    unsigned sizes[] = {1u, 5u, 33u, 1000u};
    for(int i=0;i<4;i++) printf("round_up_pow2(%u) = %u\n", sizes[i], round_up_pow2(sizes[i]));
    printf("align_up(4097, 4096) = %u\n", align_up(4097u, 4096u));
    return 0;
}

Line by line

Common mistakes

Off-by-one (missing the x--); assuming alignment a can be non-power-of-two.

Debugging tips

Compiler errors and warnings:

• warning: right shift count >= width of type — you added a >> 32 step to a 32-bit version (that step belongs only in the 64-bit variant).
• No warning for a non-power-of-two alignment; that failure is silent.

Runtime symptoms:

• An exact power of two doubles. You dropped the x--; round_up_pow2(1024) returns 2048.
• Zero returns 0 instead of 1. The x <= 1 guard is missing; smearing 0-1 = 0xFFFFFFFF then adding 1 wraps to 0.
• align_up gives nonsense. The alignment is not a power of two — a - 1 is then not a low-bit mask, so the AND clears the wrong bits.
• A huge input wraps to a small result. x + a - 1 overflowed. Validate the range for untrusted input.

Technique: test 0, 1, 2, an exact power of two, and one below/above it. Those five inputs expose every bug in this lesson.

Memory safety

This lesson sits directly on top of real memory-safety machinery, so the stakes are higher than usual:

• Alignment is a correctness requirement. Many architectures fault on misaligned loads, and in C an object accessed through a misaligned pointer is undefined behaviour even on forgiving hardware. Use alignof/aligned_alloc for real allocations rather than hand-rolled pointer arithmetic.
• Overflow in x + a - 1. For untrusted sizes this can wrap and produce a smaller result — the classic precursor to an undersized allocation and a heap overflow. Check x <= UINT_MAX - (a - 1) before adding.
• Rounding a size up can overflow too. round_up_pow2 of anything above 0x80000000 has no representable answer; decide whether to clamp or reject.
• The power-of-two precondition. If a comes from configuration or input, assert a != 0 && (a & (a-1)) == 0 before using it — otherwise the mask is wrong and the alignment guarantee quietly evaporates.

Real-world uses

Concrete uses: malloc implementations round requests up to a size class. Hash tables and ring buffers size themselves to powers of two so indexing is & (n-1). Filesystems round file sizes to block boundaries. GPU and DMA buffers must be aligned to hardware-specified boundaries. Page-aligning an address with align_up(addr, 4096) is standard in virtual-memory code.

Professional best practices:

Beginner:

• Memorise the two formulas and always test the exact-power and zero cases.
• Never use align_up with an alignment you have not verified is a power of two.

Intermediate:

• Check for overflow before rounding untrusted sizes — this is a security boundary, not a nicety.
• Prefer aligned_alloc/posix_memalign and alignof over manual pointer rounding for real allocations.
• If you rely on power-of-two capacity to mask instead of divide, assert the capacity at construction so the invariant is enforced once rather than assumed everywhere.

Practice tasks

1. (Beginner) Round up to a power of two. Implement round_up_pow2 including the x <= 1 guard and the x--. Example: 1000 → 1024; 1024 → 1024; 0 → 1. Concepts: bit smearing, idempotence.

2. (Beginner) Align up. Implement align_up(x, a) for power-of-two a. Example: align_up(13,8) → 16; align_up(16,8) → 16. Concepts: low-bit masks.

3. (Intermediate) Validate the precondition. Extend align_up to return 0 (or assert) when a is not a power of two. Requirements: reuse the power-of-two test from the popcount lesson. Concepts: defensive preconditions.

4. (Intermediate) Overflow-safe rounding. Write int safe_align_up(unsigned x, unsigned a, unsigned *out) returning 0 on overflow instead of wrapping. Requirements: must reject values where x + a - 1 would wrap. Concepts: integer-overflow checks, allocation safety.

Summary

Bit smearing turns any value into the next power of two — decrement, propagate the top bit downward with shifts of 1, 2, 4, 8 and 16, then add one — where the leading decrement is what keeps exact powers of two unchanged. Aligning up is (x + a - 1) & ~(a - 1), valid only when a is a power of two because only then is a - 1 a clean low-bit mask. Both need guarding: zero and one for the rounding, the power-of-two precondition for the alignment, and an overflow check whenever the value is untrusted, since a wrapped size is how undersized allocations become heap overflows.

Practice with these exercises

• Round up to a power of two
• Align up to a boundary