問(wèn)題描述

我需要找到大于或等于給定值的 2 的最小冪.到目前為止，我有這個(gè):

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;

它工作正常，但感覺(jué)有點(diǎn)天真.有沒(méi)有更好的算法來(lái)解決這個(gè)問(wèn)題?

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

編輯.有一些不錯(cuò)的匯編程序建議，所以我將這些標(biāo)簽添加到問(wèn)題中.

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

推薦答案

這是我最喜歡的.除了對(duì)它是否無(wú)效的初始檢查(<0，如果你知道你只傳入了 >=0 的數(shù)字，你可以跳過(guò)它)，它沒(méi)有循環(huán)或條件，因此將優(yōu)于大多數(shù)其他方法.這與 erickson 的答案類(lèi)似，但我認(rèn)為我在開(kāi)頭遞減 x 并在結(jié)尾加 1 比他的答案少一些尷尬(并且也避免了結(jié)尾的條件).

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

這篇關(guān)于查找大于或等于給定值的 2 的最小冪的算法的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，也希望大家多多支持html5模板網(wǎng)！