求大于等于一个给定数的、最小的 2的幂，有一句话的方法吗？

如题，给定一个数，求大于等于它的、最小的2的幂，例如

1 ==> 1
2 ==> 2
3 ==> 4
4 ==> 4
5 ==> 8
6 ==> 8
7 ==> 8
8 ==> 8
9 ==> 16
10 ==> 16
……

有简洁的表达方法吗？
最好是一句话，别用循环

24 个解决方案

#1

int fun(int i)
{
	int ret=0;
	while (i)
	{
		i=(i>>1);
		++ret;
	}
	return ret;
}

#2

转化二进制，
除了1之外，如果这个数在二进制情况下只有一位为1，其他位为0，那么就是这个数为结果，
否则取其最高位的后一位为1其余为0这个数为结果。

#3

不用循环貌似有难度

#4

引用 2 楼 chin_chen 的回复:

转化二进制， 
除了1之外，如果这个数在二进制情况下只有一位为1，其他位为0，那么就是这个数为结果， 
否则取其最高位的后一位为1其余为0这个数为结果。

有一句话代码吗？

#5

如果是循环，希望能比我这个快：

    int GetWellSize(int nTotalSize)
    {
        size_t bits = sizeof(int) << 3;

        int ret = 1 << (bits - 2);

        while (bits /= 2)
        {
            if ((ret >> bits) >= nTotalSize)
            {
                ret >>= bits;
            }
        }

        return ret;
    }

另外，“最小”不用非常严格，有规律地差一点点没关系，但大于给定数要保证

#6

int fun(int i)
{
	return pow(2, ceil((log((double)i)/log((double)2))));

}

#7

我那个位循环的只是输出2的多少次方。

上面的纯数学函数。。。符合你的一句话要求了

#8

引用 6 楼 downmooner 的回复:

C/C++ codeint fun(int i)
{
    return pow(2, ceil((log((double)i)/log((double)2))));

}

貌似可以了吧。

#9

size_t x;
cin>>x;
cout<<(int)(log(x)/log(2))<<endl; 

#10

              

dest = (log2(n)-(int)log2(n))==0 ? n : 2^((int)log2(n) );

呵呵，开心一下matlab code

#11

谢谢各位热心朋友

不过我的原意是开销要小，用数学函数的话，那还不如自己拿来循环呀

#12

1楼就够用了，我在嵌入式代码中都那样写的，跑起来也还行

还有，刚刚我还写错了，改下：

dest = (log2(n)-(int)log2(n))==0 ? 2^n : 2^((int)log2(n) );

#13

楼主你确定答案既没用循环 也没用简单数学函数？


等待高手

#14

int fun(int i)
{
	int ret=1;
	while (i)
	{
		i>>=1;
		ret<<=1;
	}
	return ret;
}

差不多就是这个了

#15

引用 13 楼 downmooner 的回复:

楼主你确定答案既没用循环 也没用简单数学函数？ 

等待高手

这不是题目

是我自己突然很想知道有没有巧妙的方法

1 楼的不比我在 5 楼给出的要好

#16

1楼只是随便写下思路啊。

看14楼的。

你的循环里有if。。。。按照更底层的叫什么CPU流水线中断。。


还有我的是位操作。。

#17

引用 16 楼 downmooner 的回复:

循环里有if
按照更底层的叫什么CPU流水线中断。。

还有我的是位操作。。

是的，一般对于嵌入式行业的处理器就是这样的，如ARM，MIPS，PowerPC，这些都是RISC结构，对于CISC结构的应用，如普通的桌面就无所谓了。

另外，现在编译器对于这点已经优化的差不多了

#18

Hacker's Delight, 3-2
Rounding Up
The right-propagation trick yields a good algorithm for rounding up to the next power of 2. This algorithm, shown in Figure 3-3, is branch-free and runs in 12 instructions.

Figure 3-3 Least power of 2 greater than or equal to x.

unsigned clp2(unsigned x) {
   x = x - 1; 
   x = x | (x >> 1); 
   x = x | (x >> 2); 
   x = x | (x >> 4); 
   x = x | (x >> 8); 
   x = x | (x >>16); 
   return x + 1; 
} 

#19

引用 18 楼 *mill 的回复:

C/C++ codeHacker's Delight, 3-2Rounding Up
The right-propagation trick yields a good algorithmforrounding up to the next power of2. This algorithm, showninFigure3-3,isbranch-free and runsin12instructions.

Figure3-3Least power of2greater than or equal to x.

unsigned clp2(unsigned x) {
   x=x-1; 
   x=x|(x>>1); 
   x=x|(x>>2); 
   x=x|(x>>4); 
   x=x|(x>>8); 
   x=x|(x>>16);returnx+1; 
}

估计还有种方法。建个结构体或者uniou。类似于字节序转换那样。。。说不定可以不通过函数就可以得出来。

#20

"Hacker's Delight", 3-2

An attempt to compute this with the obvious loop does not work out very well:

y = 1; 
while (y < x)     // Unsigned comparison. 
   y = 2*y;  // 用y <<= 1;可能好一点，不过编译器应该能做这个优化
return y; 

This code returns 1 for x = 0, which is probably not what you want,
loops forever for x 231,
and executes in 4n +3 instructions, where n is the power of 2 of the returned integer.
Thus, it is slower than the branch-free code, in terms of instructions executed, for n 3 (x 8).

#21

受教育了。。。。一步一个脚印啊

#22

18 楼的不错，
20 楼的本是最先想到的，折腾了这么久，发现最原始的反而比后来折腾出来的简洁多了
效率上，似乎还是 18 楼的好


我分数太少了，再晾一两天加分结，都有份。

希望有更精彩的^_^

#23

不对。。。刚看了下，我不够 100 可用分了。。。

#24

大家去Hacker's Delight这上面瞅瞅吧，还有一些挺BT的算法，挺佩服这些人的