C++ 如何有效地检索数字的第一位十进制数字
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17393757/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to retrieve the first decimal digit of number efficiently
提问by mohit
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';
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).
哪些是其他方式（效率是首要考虑的问题）？
我见过这个，除了我只需要找到第一个数字。（另外，我不明白答案）。
回答by anatolyg
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.
一些处理器具有非常快速地计算数字“多大”的指令（参见http://en.wikipedia.org/wiki/Leading_zero_count）。这可以用来快速选择一个 10 的幂，然后除以它，而不是重复除以 10。
Suppose you are given a function clzthat 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.
假设您有一个函数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;
}
回答by MrSmith42
e.g. for in 32 bit unsigned:
例如对于 32 位无符号：
Step 1:determine (by binary search) in which of the following intervals the value is:
步骤 1：确定（通过二分搜索）该值在以下哪个区间中：
0 .. 9
10 .. 99
100 .. 999
1000 .. 9999
10000 .. 99999
100000 .. 999999
1000000 .. 9999999
10000000 .. 99999999
100000000 .. 999999999
1000000000 .. 4294967295
takes max 4 compares
最多需要 4 次比较
Step 2:
第2步：
Than calculate the leading digit by one division.
比以一格计算前导数字。
回答by Mats Petersson
I'm pretty sure that sprintf(as I assume it is) will be SIGNIFICANTLY slower. You could do some optimization to reduce the number of divide operations (which is one of the slowest instructions on nearly all processors).
我很确定sprintf（正如我认为的那样）会明显变慢。您可以进行一些优化以减少除法运算的数量（这是几乎所有处理器上最慢的指令之一）。
So one could do something like this:
所以可以做这样的事情：
while(n > 10000)
n /= 1000;
while(n >= 9)
n /= 10;
That is, of course, if speed is really important.
当然，如果速度真的很重要的话。
回答by Mihai Maruseac
Your second example should use sprintf. Anyway, it cannot be faster since the entire number is printed, thus all digits are searched.
你的第二个例子应该使用sprintf. 无论如何，由于打印了整个数字，因此不会更快，因此搜索所有数字。
The linked question/answer uses a property of logarithm: for a number of xdigits, it's base 10 logarithm is between xand x+1. But, due to floating point errors this method doesn't really work properly in some cases. Also, take into consideration the fact that doing floating point is slower than doing integer arithmetic.
链接的问题/答案使用对数属性：对于多个x数字，它的底数为 10 的对数介于x和之间x+1。但是，由于浮点错误，此方法在某些情况下无法正常工作。另外，考虑到浮点运算比整数运算慢这一事实。
Thus, the simplest solution is also the faster.
因此，最简单的解决方案也更快。
回答by Gianluca Ghettini
you can do it in O(1) constant time but at expense of a very large memory usage. It's the same old time/memory trade off.
你可以在 O(1) 常数时间内完成，但代价是非常大的内存使用量。这是同样的旧时间/内存权衡。
You can create a lookup table of 2^31 entries (signed int), 4 bits per entry (with 4 bits you can encode the first digit 1-9 of the number in decimal representation).
您可以创建一个包含 2^31 个条目（带符号整数）的查找表，每个条目 4 位（使用 4 位您可以以十进制表示形式对数字的第一个数字 1-9 进行编码）。
then you can use you int to access the lookup table and get the first digit in O(1). the lookup table will take 2^31 * 4 bits -> 1024 Mbytes
然后您可以使用 int 访问查找表并获取 O(1) 中的第一个数字。查找表将占用 2^31 * 4 位 -> 1024 MB
it's the fastest way I can think of...
这是我能想到的最快的方法...
回答by S Jain
You Can Do simply This :
你可以简单地这样做：
//Shashank Jain
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int num,fdigit;
cin>>num;
if(num<0)
num*=-1;
int l=log10(num); // l = (length of number -1)
fdigit=num/pow(10,l);
cout<<fdigit<<endl;
return 0;
}
回答by Mark Ransom
Here's a kind of variation on a binary search. Like a binary search it is O(log n). Whether it's faster will depend on how fast you can do integer division.
这是二分搜索的一种变体。就像二进制搜索一样，它是 O(log n)。它是否更快将取决于您进行整数除法的速度。
if (n >= 100000000)
n /= 100000000
if (n >= 10000)
n /= 10000
if (n >= 100)
n /= 100
if (n >= 10)
n /= 10
The method expands easily for integers with a larger range.
该方法很容易扩展到更大范围的整数。
回答by Dumitriu Sebastian
int FirstDigit ( int Number ) {
// to obtain the <number of digits -1> use this math formula:
int DigitsInNumber = (int) lg(Number);
long TenExpon = pow(10, DigitsInNumber);
return (Number / TenExpon); //first digit
}
also: lg(n) = ln(n) / ln(10);
还： lg(n) = ln(n) / ln(10);
回答by TonyK
Your first solution (assuming that n is known to be >= 0) is nearly optimal, and I think it could only be substantially improved by using in-line assembly language. But that would only be worthwhile if you were processing millions of such numbers.
您的第一个解决方案（假设已知 n >= 0）几乎是最优的，我认为它只能通过使用内嵌汇编语言得到实质性改进。但这只有在您处理数百万个这样的数字时才值得。
Your second solution is -- how can I put this nicely? -- more of a Java-ish approach: Performance? La-di-da, who cares...
你的第二个解决方案是——我怎么能把这个说得好？-- 更多的是 Java 风格的方法：性能？拉迪达，谁在乎...
回答by Afrah
for(int i=0; i<n; i++)
{
e=5; //Specify the number of digits in the number OR Exponential value of 10
while(e>=0)
{
tenp=pow(10,e); //#include <math.h>
if(arr[i]/tenp!=0)
{
q[i][e]=arr[i]/tenp%10;
}
e--;
}
}However, this code's complexity shall be O(n^2), which in undesirable.
然而，这段代码的复杂度应该是 O(n^2)，这是不可取的。
