Efficient computation of a power of 2

Question

I have a requirement to compute k as the smallest power of 2 which is >= an integer value, n (n is always > 0)

currently I am using:

#define log2(x) log(x)/log(2)
#define round(x) (int)(x+0.5)

k = round(pow(2,(ceil(log2(n)))));

this is in a performance critical function

Is there a more computationally efficient way of calculating k?

Answer 1

/* returns greatest power of 2 less than or equal to x, branch-free */
/* Source: Hacker's Delight, First Edition. */
int
flp2(int x)
{
    x = x | (x>>1);
    x = x | (x>>2);
    x = x | (x>>4);
    x = x | (x>>8);
    x = x | (x>>16);
    return x - (x>>1);
}

It's entertaining to study it and see how it works. I think the only way for you to know for sure which of the solutions you see will be optimal for your situation is to use all of them in a text fixture and profile it and see which is most efficient for your purpose.

Being branch-free, this one is likely to be quite good performance-wise relative to some others, but you should test it directly to be sure.

If you want the least power of two greater than or equal to X, you can use a slightly different solution:

unsigned
clp2(unsigned x)
{
    x = x -1;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    return x + 1;
}

Answer 2

int calculate_least_covering_power_of_two(int x)
{
  int k = 1;
  while( k < x ) k = k << 1;
  return k;
}