c++ - 如何有效地检索数字的第一个十进制数字

Question

一个明显的解决方案是:

int n = 2134;
while(n > 9)
    n /= 10;

这需要线性时间。我们能做得更快吗？

这是否比线性时间快:

char s[100];
sprintf(s, "%d", n);
n = s[0]-'0';

还有哪些其他方式(效率是首要考虑)？
我看过this ，除了我只需要找到第一个数字。(另外，我不明白答案)。

Answer 1

一些处理器有指令可以非常快速地计算一个数字的“大小”(见 http://en.wikipedia.org/wiki/Leading_zero_count)。这可以用来快速选择 10 的幂，然后除以它，而不是重复除以 10。

假设您有一个函数 clz，它计算数字二进制表示 (0...32) 中前导零位的数量。然后，您可以使用一个查找表，为每个前导零数提供 10 的适当幂。

uint32_t powers_of_10[33] = {
    1000000000, 1000000000,
    100000000, 100000000, 100000000,
    10000000, 10000000, 10000000,
    1000000, 1000000, 1000000, 1000000,
    100000, 100000, 100000,
    10000, 10000, 10000,
    1000, 1000, 1000, 1000,
    100, 100, 100,
    10, 10, 10,
    1, 1, 1, 1, 1
};

int CalcFirstDecimalDigit(uint32_t x)
{
    int leading_zeros = clz(x);
    x /= powers_of_10[leading_zeros];
    if (x >= 10)
        return 1;
    else
        return x;
}