dengxf同学提到的一个问题，想了一下，想到的一个算法：

令x为已知量，y为目标量，k为迭代轮数，

1: 令y=x-1，k=0
2: 对于 y 右移 2^k 位 > 0的情形，执行下列操作，直到此条件不符合为止：
y与前述结果相与；k累进1。
3: y累进1。

原理：第(2)步的循环将除最高位的所有0均置位。最后一步(3)修正这一值。

但是感觉不太好，有没有更好的办法呢？

Archived: 9 Comments

小狼诺夫 | October 8, 2006 9:59 AM

可以用一个数组把2的n次方(n自定义)之内的值保存起来，然后遍历就可以了。

hoxide | October 8, 2006 6:38 PM

用ceil(log(n)/log(2))

Xin LI | October 8, 2006 10:55 PM

To 小狼诺夫：你的方法需要访问连续的字长*n个内存单元，这种做法对性能的影响还是挺大的……

Xin LI | October 8, 2006 10:59 PM

To hoxide：我认为这个方法不太好。浮点运算的开销相当大，如果这是一条热路径，这会损失性能。

antijp | October 9, 2006 8:46 AM

不太明白k是干什么的，是你的算法中使用的还是其他的什么？

不知道flsl可以用么？flsl(x)和flsl(x-1)，然后判断一下（这个方法不太通用，ia32和ia64以及amd64比较高效）

iamqk | October 9, 2006 10:49 PM

如果使用分段的方式来进行判断会不会快些？比如int型的整数，先取其前十六位判断是否为零，如果是判断另外的十六位中的高八位，如果否，继续在这个十六位中的高八位继续进行，类似二分法不过不清楚取位的时候效率高不高，不过总的来说会少些循环过程

dengxf | October 13, 2006 9:58 AM

一个朋友给了一个利用浮点数的实现，我修改了其中的if判断，利用取反来完成。

unsigned int get2m2(unsigned int x)
{
unsigned int i;
unsigned int mv;
float f;

f = x;
i = *((unsigned int *)(&f));
mv = ((i » 23) & 0xFF) - 126;
mv -= !(i & 0x7FFFFF);
return (1 « mv);
}

dengxf | October 14, 2006 1:01 AM

晚上想到一个:
unsigned int get2m(unsigned int x)
{
unsigned int m = 0;

m += !(x & 0xFF000000) « 3;
m += !((x « m) & 0xFF000000) « 3;
m += !((x « m) & 0xFF000000) « 3;
m += !((x « m) & 0xF0000000) « 2;
m += !((x « m) & 0xC0000000) « 1;
m += !((x « m) & 0x80000000);

m += !((x « m) & 0x7FFFFFFF);

return (1 « (32-m));
}

另外fb 7的malloc.c里面的实现:
static inline size_t
pow2_ceil(size_t x)
{

x–;
x |= x » 1;
x |= x » 2;
x |= x » 4;
x |= x » 8;
x |= x » 16;
#if (SIZEOF_PTR == 8)
x |= x » 32;
#endif
x++;
return (x);
}

我测试了一些。这两个函数在gcc未优化的时候，下面的好一些。优化的时候，性能持平。

antijp | October 15, 2006 4:21 PM

用bsr指令的话，在EM64T Xeon上面比那个x |= x » n的慢10%左右，但是用了Pentium M的话，可以快30%左右，不知道使用core的会怎么样。