c - 高效计算 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);
}

研究它并了解它是如何工作的很有趣。我认为，要确定您看到的哪种解决方案最适合您的情况，唯一的方法是在文本固定装置中使用所有这些解决方案并对其进行分析，看看哪种解决方案最适合您的目的。

作为无分支，相对于其他一些，这个在性能方面可能相当不错，但您应该直接测试它以确保。

如果您想要大于或等于 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;
}