获取一个十进制数的最高位

Algorithm

Algorithm C/C++ Stackoverflow

Feb 13, 2016

整理来自于Stackoverflow的这里http://stackoverflow.com/questions/701322/how-can-you-get-the-first-digit-in-an-int-c/701621#701621。

问题描述：在给定的一个十进制的整数，如何能够快速的求得其十进制的最高位数值是多少？

Method 1

利用to_string函数，将整数强制转换为string类型，然后取数组中第一个字符，再将之转换为int类型。

//Method 1
int Fn_Get_First_By_String(unsigned long n){
    return ((int) (to_string(n)[0])) - '0';
}

很简单的一种思路，想当然的想法，但其效率肯定会很差的。

Method 2

利用math中库函数，直接用整数除以不大于该整数最大的10的整数幂值，来获取其商。

//Method 2
int Fn_Get_First_By_MathFunc(unsigned long n){
    return (int)(n / pow(10, floor(log10(n))));
}

数学思路，比如11/10商1， 321/100 商3，非常简单，也没什么可讲的。不过需要注意一点是log函数的参数必须为正值，如果测试代码中包含0的话需要特别处理下。处理后应该如下：

int Fn_Get_First_By_MathFunc(unsigned long n){
    return n <= 0 ? 0 : (int)(n / pow(10, floor(log10(n))));
}

Method 3

前两类方法都是利用外部函数调用，相较而言速度肯定会比较慢的。这里有一种相对速度较快的，也是比较好想的方法。通过整除10的方法来循环得到整数的各位以及最高位。

//Method 3
int Fn_Get_First_By_Looping(unsigned long n){
    while(n >=10)
        n /= 10;
    return n;
}

时间复杂度跟整数的十进制最高位数成正比。

Method 4

条件判断法。

因为我们知道一个整数在计算机的存储中范围是有限的。那我们就分情况来讨论该整数最邻近的10的指数幂，然后利用整除方式得到最高位值。

// Method 4
int Fn_Get_First_By_Conditional(unsigned long n){
    int digit = 0;
    if( n<10 )
        digit = n;
    else if( n<100 )
        digit = n/10;
    else if( n<1000 )
        digit = n/100;
    else if( n<10000 )
        digit = n/1000;
    else if( n<100000 )
        digit = n/10000;
    else if( n<1000000 )
        digit = n/100000;
    else if( n<10000000 )
        digit = n/1000000;
    else if( n<100000000 )
        digit = n/10000000;
    else if( n<1000000000 )
        digit = n/100000000;
    else
        digit = n/1000000000;
    return digit;
}

可以看到，代码是最长的一个，因为我们需要讨论从1到最大范围内的10的幂值，但相对其他方式来说速度也是很快的。

Method 5

最后这个方法堪称完美。

//Method 5
int Fn_Get_First_By_Unrolled_Optimized(unsigned long n){
    if( n>=100000000 ) n /= 100000000;
    if( n>=10000 ) n /= 10000;
    if( n>=100 ) n /= 100;
    if( n>=10 ) n /= 10;
    return n;
}

巧妙的利用二分法将Method 4中的条件进一步拆解。最高可以处理到(10^16 - 1)的数值。比如说3872865，首先经过第二个if剩下387，然后第三个if后得到38，最后一个if则出来最终结果3。简洁凝练迅速，太完美了。

性能对比

通过测试代码，for循环从0到10^9次，间隔为5，统计所有数的最高位数的总和。结果如下所示:

Fn_Get_First_By_String Result: 999999996, Time: 48.2231
Fn_Get_First_By_MathFunc Result: 999999996, Time: 32.8894
Fn_Get_First_By_Looping Result: 999999996, Time: 8.66428
Fn_Get_First_By_Conditional Result: 999999996, Time: 2.68092
Fn_Get_First_By_Unrolled_Optimized Result: 999999996, Time: 1.87899

还是方法5的速度最快。而第一种方式跟第二种方式由于调用外部函数，很是耗时。

13 Feb 2016

Post by: MetaCoder