NEXT POWER OF TWO smear every bit downward, then add one — the next 2^k in five ORs
To round a number up to the next power of two, you flood all the bits below the highest set bit, then add one. Take n−1, then n |= n>>1; n |= n>>2; n |= n>>4; … — each OR doubles the run of 1s, so after a logarithmic number of steps every bit below the top is set: the value is 2^k − 1. Add one and you land exactly on the next power of two. It is the branchless bit-smear behind every buffer that grows by doubling and every hash table that resizes to a power of two.
THE TECHNIQUE n−1, then OR down by 1,2,4,8,16, then +1
The demo rounds 37 up to 64 by smearing the bits of 36 down to 63, then adding one: live demo
HISTORY & CREDIT Hart & Lewis 1997 · Anderson 2001
“Next power of two needs a log and a shift.” — it needs a bit-smear: OR the value onto itself shifted, then +1. cited
the smear · n |= n>>k for k=1,2,4,8,16 — the run of 1s below the top bit doubles each OR. the fill · after log-many ORs every lower bit is set: 2^k − 1 — then +1 is the power. 1997 / 2001 · the shift-or method: Pete Hart & William Lewis (1997), popularized by Sean Anderson’s Bit Twiddling Hacks (~2001); also Warren’s Hacker’s Delight. Do n−1 first so exact powers map to themselves.
Every low bit flooded on, then one added — the next power of two with no loop bound and no log. resource
RECOMMEND FOR I-13 the bit-smear, on the compiler
On the canonical compiler, smearing 36 fills it to 63, and +1 gives 64 — the next power of two above 37:
$ i13 run tk_roundup.i13 # (n-1) |= (n-1)>>k for k=16..1, then +1
RUN OK · 106 step(s) · peak stack 4 · call depth 6
n = 37
m = 36 -- n-1
s = 63 -- all lower bits smeared on (2^6 - 1)
pw = 64 -- +1 -> next power of two
same = 1
Recommend as a NULL — resource, the branchless kind. Next-power-of-two returns the same value a loop (“double until ≥ n”) would give — i13 prints 64 — but with no data-dependent branch, just a fixed cascade of ORs. The win is branchlessness and fixed latency, both resource (B40), not a change to the output relation. NULL. It is the batch’s cleanest “replace a loop with a straight-line bit cascade” case, and it leans on the-log2 (419) conceptually.