# Algorithm for finding the smallest power of two that's greater or equal to a given value

### Question

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.

1
47
12/17/2008 1:41:29 AM

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;
}
``````
62
12/13/2008 10:08:55 AM

``````ceil(log2(value))
``````

`ilog2()` can be calculated in 3 asm instructions e.g., http://www.asterisk.org/doxygen/1.4/log2comp_8h-source.html