高效计算2的幂

Question

我要求计算k为2的最小幂,> =整数值,n(n总是> 0)

目前我正在使用:

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

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

这是一个性能关键的功能

是否有更高计算效率的计算方法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);
}

研究它并了解它是如何工作的,这很有趣.我认为唯一可以让您确定哪种解决方案最适合您的情况的方法是在文本夹具中使用所有这些解决方案并对其进行分析并查看哪种解决方案最适合您的目的.

由于没有分支,这个可能在性能方面相对于其他一些非常好,但你应该直接测试它以确保.

如果您希望2的最小幂大于或等于X,则可以使用稍微不同的解决方案:

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;
}