delphij's Chaos

选择chaos这个词是因为~~实在很难找到一个更合适的词来形容这儿了……

08 Oct 2006

如何计算不小于给定数的最小的2整数次方幂?

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的会怎么样。