给定n = 2 ^ k,我如何找到k假设n是32位整数,使用C/C++按位？
解决方法
好吧,您可以使用二进制指数显式存储在浮点数中的事实：
unsigned log2(unsigned x)
{
float f = x;
memcpy(&x,&f,sizeof x);
return (x >> 23) - 127;
}
我不知道这有多快,它肯定不是最便携的解决方案,但我发现它非常有趣.
只是为了好玩,这是一个完全不同的,相对简单的解决方案：
unsigned log2(unsigned x)
{
unsigned exp = 0;
for (; ;)
{
switch (x)
{
case 128: ++exp;
case 64: ++exp;
case 32: ++exp;
case 16: ++exp;
case 8: ++exp;
case 4: ++exp;
case 2: ++exp;
case 1: return exp;
case 0: throw "illegal input detected";
}
x >>= 8;
exp += 8;
}
}
这是一个完全展开的解决方案：
#define CASE(exp) case (1 << (exp)) : return (exp);
unsigned log2(unsigned x)
{
switch (x)
{
CASE(31) CASE(30) CASE(29) CASE(28)
CASE(27) CASE(26) CASE(25) CASE(24)
CASE(23) CASE(22) CASE(21) CASE(20)
CASE(19) CASE(18) CASE(17) CASE(16)
CASE(15) CASE(14) CASE(13) CASE(12)
CASE(11) CASE(10) CASE( 9) CASE( 8)
CASE( 7) CASE( 6) CASE( 5) CASE( 4)
CASE( 3) CASE( 2) CASE( 1) CASE( 0)
default: throw "illegal input";
}
}
