如何有效地检索号的第一位数 [英] How to retrieve the first digit of number efficiently
问题描述
一个显而易见的解决方案是:
One obvious solution is:
int n = 2134;
while(n > 9)
n /= 10;
这需要线性时间。我们能不能做任何更快?
which takes linear time. Could we do any faster?
这是任何速度比线性时间:
Is this any faster than linear time:
char s[100];
sprintf(s, "%d", n);
n = s[0]-'0';
这是其他方法(效率是首要关注的问题)?
我已经看到了<一个href="http://stackoverflow.com/questions/4525121/first-n-digits-of-a-long-number-in-constant-time">this,但我需要找到只有第一个数字。
(另外,我不明白的答案)。
Which are the other ways (efficiency is primary concern)?
I've seen this, except that I need to find only the first digit.
(Also, I don't understand the answer).
推荐答案
一些处理器具有计算有多大一个数字是,很快说明(见<一href="http://en.wikipedia.org/wiki/Leading_zero_count">http://en.wikipedia.org/wiki/Leading_zero_count).这可以用于快速选择10的幂,并通过将其除以代替由10重复进行分流,
Some processors have instructions that calculate "how big" a number is, very quickly (see http://en.wikipedia.org/wiki/Leading_zero_count). This can be used to quickly choose a power of 10, and divide by it, instead of dividing by 10 repeatedly.
假设给你一个函数 CLZ
,计算在一个数字的二进制重新presentation(0 ... 32)前导零的位数。然后,你可以使用一个查找表,给出了10的前导零的每个号码适当的电源。
Suppose you are given a function clz
that calculates the number of leading zero bits in a number's binary representation (0...32). Then, you can use a lookup table that gives the proper power of 10 for each number of leading zeros.
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;
}
这篇关于如何有效地检索号的第一位数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!