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

Question

一个明显的解决方案是

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

这需要线性时间.我们可以做得更快吗？

这比线性时间快吗:

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

其他方式是什么(效率是首要考虑因素)？
我见过这个,除了我只需要找到第一个数字.(另外,我不明白答案).

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;
}

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个比较

第2步:

比一个师计算领先数字.

Answer 3

我很确定sprintf(我认为是这样)会慢得多.您可以进行一些优化以减少除法运算的数量(这是几乎所有处理器上最慢的指令之一).

所以可以这样做:

 while(n > 10000)
   n /= 1000;

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

当然,如果速度非常重要的话.

Answer 4

你的第二个例子应该使用sprintf.无论如何,由于打印整个数字,它不能更快​​,因此搜索所有数字.

链接的问题/答案使用对数属性:对于多个x数字,它的基数10对数在x和之间x+1.但是,由于浮点错误,此方法在某些情况下无法正常工作.另外,考虑到执行浮点比执行整数运算慢的事实.

因此,最简单的解决方案也更快.