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

Question

一个显而易见的解决方案是：

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

这需要线性时间。我们能再快点吗？

这比线性时间快吗

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

还有哪些方法（效率是首要考虑的）<我见过这个，只是我只需要找到第一个数字。（还有，我不明白答案）。

Answer 1

我很确定sprintf（我认为是这样）会明显变慢。您可以进行一些优化以减少除法运算的数量（这是几乎所有处理器上最慢的指令之一）。

所以我们可以做这样的事情：

 while(n > 10000)
   n /= 1000;

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

当然，如果速度真的很重要的话。

Answer 2

例如，对于32位无符号：

步骤1：确定（通过二进制搜索）该值在以下哪个时间间隔内：

0 .. 9
10 .. 99
100 .. 999
1000 .. 9999
10000 .. 99999
100000 .. 999999
1000000 .. 9999999
10000000 .. 99999999
100000000 .. 999999999
1000000000 .. 4294967295

最多4次比较

第二步：

比计算前导数字除以一。

Answer 3

一些处理器的指令可以快速计算一个数字的“大小”（参见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;
}