我有一个需求,需要计算k
,使其成为大于等于整数n
的最小2的幂次方(n
始终大于0)。
目前我正在使用以下方法:
#define log2(x) log(x)/log(2)
#define round(x) (int)(x+0.5)
k = round(pow(2,(ceil(log2(n)))));
这是一个性能关键的函数。
有没有更加计算效率更高的方式来计算 k
?
我有一个需求,需要计算k
,使其成为大于等于整数n
的最小2的幂次方(n
始终大于0)。
目前我正在使用以下方法:
#define log2(x) log(x)/log(2)
#define round(x) (int)(x+0.5)
k = round(pow(2,(ceil(log2(n)))));
这是一个性能关键的函数。
有没有更加计算效率更高的方式来计算 k
?
/* returns greatest power of 2 less than or equal to x, branch-free */
/* Source: Hacker's Delight, First Edition. */
int
flp2(int x)
{
x = x | (x>>1);
x = x | (x>>2);
x = x | (x>>4);
x = x | (x>>8);
x = x | (x>>16);
return x - (x>>1);
}
研究IT技术相关内容并了解其工作原理很有趣。我认为,想要确定哪种解决方案最适合您的情况,唯一的方法是在文本夹具中使用所有解决方案进行测试,并对其进行分析,看哪种方案最有效。
由于不涉及分支,这个方案相对于其他方案可能性能更好,但您应该直接测试以确保。
如果您想要大于或等于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;
}
lim = 123;
n = 1;
while( ( n = n << 1 ) <= lim );
将您的数字乘以2,直到它大于lim。
左移一位将值乘以2。
int CalculateK(int val)
{
int cnt = 0;
while(val > 0)
{
cnt++;
val = val >> 1;
}
return 1 << cnt;
}
int CalculateK(int val)
{
int res = 1;
while(res <= val) res <<= 1;
return res ;
}
int calculate_least_covering_power_of_two(int x)
{
int k = 1;
while( k < x ) k = k << 1;
return k;
}
x |= x>>32
来适应64位平台,并且其复杂度在最坏情况和最好情况下都是对数级别的。我的估计是,在32位系统上,RandyHoward的函数比这个函数平均快15%。 - Alex Shesterovk = 1 << (int)(ceil(log2(n)));
ceil
的类型为 double
,不能与 <<
一起使用。当插入一个 int
强制转换并且 n
为32时,此代码会产生32,但期望的结果是64。 - Eric Postpischil来源:hackersdelight.org
/* altered to: power of 2 which is greater than an integer value */
unsigned clp2(unsigned x) {
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >>16);
return x + 1;
}
x = x | (x >> 32);
适用于64位数字。
1 << CHAR_BIT * sizeof x - __builtin_clz(x)
,前提是x
具有无符号整型或在普通系统上为int
类型。对于unsigned long
类型,还有一个名为__builtin_clzl
的函数。某些非GCC编译器也支持此扩展功能。在拥有“查找第一个位设置”指令的处理器上,这将比迄今为止提供的任何其他答案更快。 - Eric Postpischil