c++ - 查找大于或等于给定值的最小幂的算法

Question

这个问题在这里已经有了答案:

Rounding up to next power of 2 (31 个回答)

关闭 5年前。

我需要找到大于或等于给定值的 2 的最小幂。到目前为止，我有这个:

int value = 3221; // 3221 is just an example, could be any number
int result = 1;

while (result < value) result <<= 1;

它工作正常，但感觉有点幼稚。有没有更好的算法来解决这个问题？

编辑。有一些很好的汇编程序建议，所以我将这些标签添加到问题中。

Answer 1

这是我最喜欢的。除了初始检查它是​​否无效(<0，如果你知道你只传入 >=0 的数字，你可以跳过它)，它没有循环或条件，因此将优于大多数其他方法。这与埃里克森的回答类似，但我认为我在开头递减 x 并在结尾添加 1 比他的回答要少一些尴尬(并且还避免了结尾的条件)。

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