如何计算不小于给定数的最小的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的会怎么样。