Here’s my favorite. Other than the initial check for whether it’s invalid (<0, which you could skip if you knew you’d only have >=0 numbers passed in), it has no loops or conditionals, and thus will outperform most other methods. This is similar to erickson’s answer, but I think that my decrementing x at the beginning and adding 1 at the end is a little less awkward than his answer (and also avoids the conditional at the end).
/// Round up to next higher power of 2 (return x if it's already a power
/// of 2).
inline int
pow2roundup (int x)
{
if (x < 0)
return 0;
--x;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x+1;
}
An answer on Given an integer, how do I find the next largest power of two using bit-twiddling? presents some explanation of how this common algorithm works, and examples of the bit-patterns for a couple inputs. (That versions uses unsigned, which allows avoiding the x<0 check and is generally better as discussed in comments.)
The same dec / shift/OR / inc strategy is found in:
- http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
- “Hacker’s Delight.” by Henry S. Warren, Jr.