log10函数返回int的性能

Question

今天我需要一个廉价的log10函数,其中我只使用了int部分.假设结果是无效的,那么999的log10将是2.自己编写函数是否有益？如果是这样,哪种方式最好去.假设代码不会被优化.

log10的替代品我虽然;

• 使用for循环除以或乘以10;
• 使用字符串解析器(可能非常昂贵);
• 使用整数log2()函数乘以常量.

先谢谢你:)

Answer 1

该操作可以在(快速)恒定时间内在具有计数前导零或类似指令(大多数体系结构)的任何体系结构上完成.这是我用来计算十进制数字位数的C片段,基本上是相同的任务(假设类似gcc的编译器和32位int):

unsigned int baseTwoDigits(unsigned int x) {
    return x ? 32 - __builtin_clz(x) : 0;
}

static unsigned int baseTenDigits(unsigned int x) {
    static const unsigned char guess[33] = {
        0, 0, 0, 0, 1, 1, 1, 2, 2, 2,
        3, 3, 3, 3, 4, 4, 4, 5, 5, 5,
        6, 6, 6, 6, 7, 7, 7, 8, 8, 8,
        9, 9, 9
    };
    static const unsigned int tenToThe[] = {
        1, 10, 100, 1000, 10000, 100000, 
        1000000, 10000000, 100000000, 1000000000,
    };
    unsigned int digits = guess[baseTwoDigits(x)];
    return digits + (x >= tenToThe[digits]);
}

GCC和clang将此编译为x86上的~10条指令.小心,人们可以在组装时更快.

关键的见解是使用(非常便宜的)基数 - 2对数来快速估计基数为10的对数; 在那一点上,我们只需要比较一个10的幂来决定我们是否需要调整猜测.这比搜索10的多个权力以找到正确的权限要有效得多.

如果输入绝对偏向于一位和两位数,则线性扫描有时会更快; 对于所有其他输入分布,这种实现往往很方便.