算法找出两个最小功率这是大于或等于给定值 [英] Algorithm for finding the smallest power of two that's greater or equal to a given value

问题描述

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

I need to find the smallest power of two that's greater or equal to a given value. So far, I have this:

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

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

它工作正常，但感觉那种天真。是否有该问题的一个更好的算法？

It works fine, but feels kind of naive. Is there a better algorithm for that problem?

编辑。有一些不错的汇编程序的建议，所以我将这些标签的问题。

EDIT. There were some nice Assembler suggestions, so I'm adding those tags to the question.

推荐答案

下面是我的最爱。除了对无论是无效的初步检查（小于0，你可以跳过，如果你知道你只要> = 0号传递），它没有循环或条件，因此将优于大多数其他的方法。这与埃里克森的答案，但我认为我的递减x开头并添加1在最后有一点比他的回答少的尴尬（也避免了条件底）。

Here's my favorite. Other than the initial check for whether it's invalid (<0, which you could skip if you knew you'd only have >=0 numbers passed in), it has no loops or conditionals, and thus will outperform most other methods. This is similar to erickson's answer, but I think that my decrementing x at the beginning and adding 1 at the end is a little less awkward than his answer (and also avoids the conditional at the end).

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

这篇关于算法找出两个最小功率这是大于或等于给定值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！