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

Question

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

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

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

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

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

原文由 Boyan 发布，翻译遵循 CC BY-SA 4.0 许可协议

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

原文由 Larry Gritz 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

递归模板版本如何生成编译常量：

 template<uint32_t A, uint8_t B = 16>
struct Pow2RoundDown { enum{ value = Pow2RoundDown<(A | (A >> B)), B/2>::value }; };
template<uint32_t A>
struct Pow2RoundDown<A, 1> { enum{ value = (A | (A >> 1)) - ((A | (A >> 1)) >> 1) }; };

template<uint32_t A, uint8_t B = 16>
struct Pow2RoundUp { enum{ value = Pow2RoundUp<((B == 16 ? (A-1) : A) | ((B == 16 ? (A-1) : A) >> B)), B/2>::value }; };
template<uint32_t A >
struct Pow2RoundUp<A, 1> { enum{ value = ((A | (A >> 1)) + 1) }; };

可以这样使用：

 Pow2RoundDown<3221>::value, Pow2RoundUp<3221>::value

原文由 duncan.forster 发布，翻译遵循 CC BY-SA 3.0 许可协议