求一个数的临近的较大的2的整数次幂

被面试官问了这么一道题..........一问，想到，左移就好了。

就会很自然的写下这种方法

代码语言：javascript复制

unsigned int f2(unsigned int val)
{
    int retval = 1;

    while (retval < val)
    {
        retval <<= 1;
    }

    return retval;
}

在改进一下，就判断他是不是2的次方先。如果是的话，可以直接返回。就可以得到这种方法。面试官又说，不能用循环递归，函数库。这下麻烦了。

代码语言：javascript复制

unsigned int f1(unsigned int val)
{
    if (val & (val - 1))//至少有两个为1的bit位
    {
        unsigned int leftmost;

        while (val)
        {
            leftmost = val;
            val &= (val - 1);
        }

        return leftmost << 1;
    }
    else
    {
        return val == 0 ? 1 : val;
    }
}

想想，如果一个数，00101 如果能找到 00100的话就好了，这样在左移一位就完事了，但是想得时候就想要求地00100的话，不就要循环了。然后就卡住了。

接着看到这个 http://blog.codingnow.com/2011/12/buddy_memory_allocation.html

就得知，还可以这么写....溜到不行。把这个数，从高位数，第一个1的右边填满，再加1...溜溜溜溜的。

代码语言：javascript复制

unsigned int f3(unsigned int val){
    {
        if (val & (val - 1)){
            val |= val>>1;
            val |= val>>2;
            val |= val>>4;
            val |= val>>8;
            val |= val>>16;
            return val 1;
        }else{
            return val == 0 ? 1 : val;
        }
    }
}

递归

0 人点赞