很棒的编程资源,Bit Twiddling Hacks,在这里提出了以下方法来计算32位整数的log2:
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
static const char LogTable256[256] =
{
-1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};
unsigned int v; // 32-bit word to find the log of
unsigned r; // r will be lg(v)
register unsigned int t, tt; // temporaries
if (tt = v >> 16)
{
r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else
{
r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}
并提到
查找表方法仅需执行大约7个操作即可查找32位值的日志。如果扩展为64位,则大约需要9次操作。
但是,可惜的是,它没有提供任何其他有关将算法扩展到64位整数的实际方法的信息。
关于这种64位算法的外观有何暗示?
qq_遁去的一_1
鸿蒙传说
相关分类