Des*_*ume 45 c lookup 64-bit bit-manipulation 32bit-64bit
一个伟大的编程资源,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位算法如何看起来的任何提示？
Des*_*ume 66
内部函数非常快,但仍然不足以实现真正的跨平台,独立于编译器的log2实现.因此,如果有人感兴趣,这里是我自己研究这个主题时遇到的最快,无分支,CPU抽象的DeBruijn算法.
const int tab64[64] = {
63, 0, 58, 1, 59, 47, 53, 2,
60, 39, 48, 27, 54, 33, 42, 3,
61, 51, 37, 40, 49, 18, 28, 20,
55, 30, 34, 11, 43, 14, 22, 4,
62, 57, 46, 52, 38, 26, 32, 41,
50, 36, 17, 19, 29, 10, 13, 21,
56, 45, 25, 31, 35, 16, 9, 12,
44, 24, 15, 8, 23, 7, 6, 5};
int log2_64 (uint64_t value)
{
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
value |= value >> 32;
return tab64[((uint64_t)((value - (value >> 1))*0x07EDD5E59A4E28C2)) >> 58];
}
向下舍入到下一个2的较低功率的部分取自2次幂边界,并且从BitScan获取尾随零的数量的部分(其中的(bb & -bb)代码是单个最右边的位,设置为1,在我们将值四舍五入到2的下一个幂之后不需要.
顺便说一句,32位实现是
const int tab32[32] = {
0, 9, 1, 10, 13, 21, 2, 29,
11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7,
19, 27, 23, 6, 26, 5, 4, 31};
int log2_32 (uint32_t value)
{
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
return tab32[(uint32_t)(value*0x07C4ACDD) >> 27];
}
与任何其他计算方法一样,log2要求输入值大于零.
kay*_*kay 46
如果您使用的是GCC,则在这种情况下不需要查找表.
GCC提供内置函数来确定前导零的数量:
内置函数: 从最高位开始,返回x中前导0位的数量.如果x为0,则结果未定义.
int __builtin_clz (unsigned int x)
所以你可以定义:
#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))
它适用于任何unsigned long long int.结果向下舍入.
对于x86和AMD64,GCC会将其编译为bsr指令,因此解决方案非常快(比查找表快得多).
工作范例:
#include <stdio.h>
#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))
int main(void) {
unsigned long long input;
while (scanf("%llu", &input) == 1) {
printf("log(%llu) = %u\n", input, LOG2(input));
}
return 0;
}
Ave*_*nar 16
我试图将O(lg(N))操作中的N位整数的日志基数2转换为乘法,并通过暴力强制查找幻数来查找 64位.不用说它需要一段时间.
然后我找到了德斯蒙德的答案,并决定尝试将他的幻数作为起点.由于我有一个6核处理器,我从0x07EDD5E59A4E28C2/6倍数并行运行它.我很惊讶它立即找到了一些东西.结果是0x07EDD5E59A4E28C2/2工作.
所以这里是0x07EDD5E59A4E28C2的代码,它可以为你节省一个移位和减法:
int LogBase2(uint64_t n)
{
static const int table[64] = {
0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61,
51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62,
57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56,
45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5, 63 };
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
return table[(n * 0x03f6eaf2cd271461) >> 58];
}
这是我为64位无符号整数所做的.这计算base-2对数的下限,相当于最高位的索引.这种方法对于大数字来说非常快,因为它使用的是一个展开的循环,它始终以log264 = 6步执行.
从本质上讲,它所做的是逐渐减去序列{0≤k≤5:2 ^(2 ^ k)} = {2³²,2¹⁶,2⁸,2⁴,2²,2¹} = {4294967296,65536,256 ,16,4,2,1}并且对减去的值的指数k求和.
int uint64_log2(uint64_t n)
{
#define S(k) if (n >= (UINT64_C(1) << k)) { i += k; n >>= k; }
int i = -(n == 0); S(32); S(16); S(8); S(4); S(2); S(1); return i;
#undef S
}
请注意,如果给出无效输入0(这是初始-(n == 0)检查的内容),则返回-1 .如果您从未期望调用它n == 0,则可以替换int i = 0;初始化程序并assert(n != 0);在函数入口处添加.
基数为10的整数对数可以使用类似的方法计算 - 最大的平方测试为10 15,因为log 102⁶⁴⁶⁴19.2659...(注意:这不是实现基数10整数对数的最快方法,因为它使用整数除法,更快的实现方法是使用具有指数增长值的累加器,并与累加器进行比较,实际上是进行一种二分搜索.)
int uint64_log10(uint64_t n)
{
#define S(k, m) if (n >= UINT64_C(m)) { i += k; n /= UINT64_C(m); }
int i = -(n == 0);
S(16,10000000000000000); S(8,100000000); S(4,10000); S(2,100); S(1,10);
return i;
#undef S
}
这是一个非常紧凑且快速的扩展，不使用额外的临时对象：
r = 0;
/* If its wider than 32 bits, then we already know that log >= 32.
So store it in R. */
if (v >> 32)
{
r = 32;
v >>= 32;
}
/* Now do the exact same thing as the 32 bit algorithm,
except we ADD to R this time. */
if (tt = v >> 16)
{
r += (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else
{
r += (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}
这是一个用 s 链构建的if，同样没有使用额外的临时对象。但可能不是最快的。
if (tt = v >> 48)
{
r = (t = tt >> 8) ? 56 + LogTable256[t] : 48 + LogTable256[tt];
}
else if (tt = v >> 32)
{
r = (t = tt >> 8) ? 40 + LogTable256[t] : 32 + LogTable256[tt];
}
else if (tt = v >> 16)
{
r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else
{
r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}
如果您正在寻找 C++ 答案，并且您找到了这里，并且由于它归结为计数零，那么您std::countl_zero根据 godbolt.org 调用得到了 which bsr。
std::countl_zero从 C++20 开始可用，您可能需要添加-std=gnu++2a到编译器命令行