
Round up to the next power of two 

Code 
01: unsigned int roundUpToNextPowerOfTwo(unsigned int x)
bits.stephanbrumme.com

Explanation 
Each number − except for zero − has at least one bit set to 1. Let's consider only the highest bit which is set to 1: If it is spread to all bit position on its right side, then we get a number which is just one below the next power of two. 00...001... → 00...001111 → increment by 1: 00...010000 A simple way to distribute this set bit is to create a sequence of rightshifted ORs. Even better, a divideandconquer strategy can be implemented branchless. Care must be taken when processing a power of 2 as it must map to itself. By default, the algorithm would give the next power of 2, however, a simple decrement by 1 (line 3) neatly solves this problem. 
Restrictions 
• designed for 32 bits • x must be positive and ≤ 2^{31}, else results are undefined 
These ads help me to pay my server bills 

Performance 
• constant time, data independent + Intel® Pentium™ D: • roundUpToNextPowerOfTwo: ≈ 13.5 cycles per number + Intel® Core™ 2: • roundUpToNextPowerOfTwo: ≈ 15 cycles per number + Intel® Core™ i7: • roundUpToNextPowerOfTwo: ≈ 14 cycles per number CPU cycles (full optimization, lower values are better) 
Assembler Output 
roundUpToNextPowerOfTwo:
bits.stephanbrumme.com

Download  The full source code including a test program is available for download. 
References 
http://graphics.stanford.edu/~seander/bithacks.html 
More Twiddled Bits 
... or go to the index 