14

一个明显的解决方案是：

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

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

这是否比线性时间快：

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

还有哪些其他方式（效率是主要关注点）？
我见过这个，除了我只需要找到第一个数字。（另外，我不明白答案）。

4

13 回答 13

22

一些处理器具有计算“有多大”数字的指令，非常快（参见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;
}
于 2013-06-30T19:46:27.117 回答
14

例如对于 32 位无符号：

第 1 步：确定（通过二分查找）该值位于以下哪个区间：

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

最多进行 4 次比较

第2步：

比以一个除法计算前导数。

于 2013-06-30T19:47:51.733 回答
6

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

所以可以做这样的事情：

 while(n > 10000)
   n /= 1000;

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

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

于 2013-06-30T19:00:38.403 回答
5

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

链接的问题/答案使用对数的属性：对于多个x数字，它的以 10 为底的对数介于x和之间x+1。但是，由于浮点错误，这种方法在某些情况下并不能真正正常工作。另外，考虑到浮点运算比整数运算要慢的事实。

因此，最简单的解决方案也更快。

于 2013-06-30T18:59:08.240 回答
4

您可以在 O(1) 恒定时间内完成此操作，但会消耗大量内存。这是相同的旧时间/内存权衡。

您可以创建一个包含 2^31 个条目（有符号整数）的查找表，每个条目 4 位（您可以使用 4 位以十进制表示形式对数字的第一个数字 1-9 进行编码）。

然后您可以使用 int 访问查找表并获取 O(1) 中的第一个数字。查找表将占用 2^31 * 4 位 -> 1024 MB

这是我能想到的最快的方法...

于 2013-06-30T19:41:35.820 回答
4

这是二分搜索的一种变体。就像二进制搜索一样，它是 O(log n)。是否更快取决于您进行整数除法的速度。

if (n >= 100000000)
    n /= 100000000
if (n >= 10000)
    n /= 10000
if (n >= 100)
    n /= 100
if (n >= 10)
    n /= 10

该方法很容易扩展到具有更大范围的整数。

于 2014-09-29T04:16:58.897 回答
3

你可以这样做：

//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;
}
于 2013-07-01T08:00:46.757 回答
1 
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
}

还：lg(n) = ln(n) / ln(10);

于 2015-07-09T18:15:25.400 回答
0

您的第一个解决方案（假设已知 n >= 0）几乎是最优的，我认为它只能通过使用内联汇编语言来大幅改进。但这只有在处理数百万个这样的数字时才值得。

你的第二个解决方案是——我怎样才能把这个很好地表达出来？——更像是一种 Java 风格的方法：性能？拉迪达，谁在乎...

于 2013-06-30T19:00:09.593 回答
0 

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

但是，此代码的复杂度应为 O(n^2)，这是不可取的。

于 2018-10-26T07:47:25.770 回答
0

另一种解决方案：以 BCD 格式存储所有值，大端。访问第一个半字节以获得第一个数字

埃斯。

Decimal value: 265
BCD format: 0010-0110-0101
于 2019-07-12T10:33:30.917 回答
-1

首先制作一个保存数字的双变量。然后在循环中将该数字除以10，使该数字连续丢失一位，直到它是一个1位数字。将 double 变量转换为 int 以将其向下舍入。结果将是先前的第一个十进制数字。

代码将以 O(log(n)) 运行。

#include <iostream>

using namespace std;

int main() {
    double a;
    cin >> a;
    while (true) {
        a /= 10;
        if (a < 10) {
            a = int(a);
            cout << a;
            break;
        }
    }
    return 0; 
}
于 2018-09-20T09:56:24.970 回答
-2

如果您的号码是 x9x8x7x6x5x4x3x2x1，那么您只需除以 10^8，因此您需要： 找出有多少位数的最佳方法。您可以使用二进制搜索/

于 2013-06-30T19:49:23.623 回答