Algorithm for finding the smallest power of two that's greater or equal to a given value [duplicate]
I need to find the smallest power of two that's greater or equal to a given value. So far, I have this:
int value = 3221; // 3221 is just an example, could be any number
int result = 1;
while (result < value) result <<= 1;
It works fine, but feels kind of naive. Is there a better algorithm for that problem?
EDIT. There were some nice Assembler suggestions, so I'm adding those tags to the question.
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;
}
ceil(log2(value))
ilog2()
can be calculated in 3 asm instructions e.g., http://www.asterisk.org/doxygen/1.4/log2comp_8h-source.html