计算速度快的日志基地2天花板 [英] Compute fast log base 2 ceiling
问题描述
什么是一个快速的方法来计算(长整型)上限(log_2(I))
,其中输入和输出的64位整数?为符号或无符号的整数解决方案是可接受的。我怀疑最好的办法将类似于这里那些被发现一个位变换的方法,但不是尝试我自己的,我想使用一些已经行之有效的。一般的解决方案将适用于所有正面的价值观。
What is a fast way to compute the (long int) ceiling(log_2(i))
, where the input and output are 64-bit integers? Solutions for signed or unsigned integers are acceptable. I suspect the best way will be a bit-twiddling method similar to those found here, but rather than attempt my own I would like to use something that is already well tested. A general solution will work for all positive values.
有关例如,对于2,3,4,5,6,7,8的值是1,2,2,3,3,3,3
For instance, the values for 2,3,4,5,6,7,8 are 1,2,2,3,3,3,3
编辑:到目前为止的最佳路线似乎是计算使用任何数目的快速现有bithacks整数/楼层数底2(与MSB的位置)或寄存器方法,然后添加一个如果输入是不二的幂。快速按位检查的两个大国是。(N及(N-1))
So far the best route seems to be to compute the integer/floor log base 2 (the position of the MSB) using any number of fast existing bithacks or register methods, and then to add one if the input is not a power of two. The fast bitwise check for powers of two is (n&(n-1))
.
另一种方法可能会尝试在指数二进制搜索电子
直到 1<&LT,E
大于或等于输入。
Another method might be to try a binary search on exponents e
until 1<<e
is greater than or equal to the input.
推荐答案
这个算法已经被公布,但下面的实现是非常紧凑的,应该优化成支自由code。
This algorithm has already been posted, but the following implementation is very compact and should optimize into branch-free code.
int ceil_log2(unsigned long long x)
{
static const unsigned long long t[6] = {
0xFFFFFFFF00000000ull,
0x00000000FFFF0000ull,
0x000000000000FF00ull,
0x00000000000000F0ull,
0x000000000000000Cull,
0x0000000000000002ull
};
int y = (((x & (x - 1)) == 0) ? 0 : 1);
int j = 32;
int i;
for (i = 0; i < 6; i++) {
int k = (((x & t[i]) == 0) ? 0 : j);
y += k;
x >>= k;
j >>= 1;
}
return y;
}
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
printf("%d\n", ceil_log2(atol(argv[1])));
return 0;
}
这篇关于计算速度快的日志基地2天花板的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!