获取整数中的数字的方法？

Question

获取整数中的数字的方法？有比这个方法更精确的方法来获得int的长度吗？int length = String.valueOf(1000).length();

Answer 1

您的基于字符串的解决方案是完全可以的，它没有“不整洁”。你必须认识到，从数学上讲，数字没有长度，也没有数字。长度和数字都是物理表征指特定基中的一个数字，即字符串。

基于对数的解决方案(有些)与基于字符串的解决方案在内部所做的事情相同，而且可能更快(不明显)，因为它只产生长度并忽略数字。但我并不认为它的意图更明确-这是最重要的因素。

Answer 2

对数是你的朋友：

int n = 1000;int length = (int)(Math.log10(n)+1);

注：只对n>0有效。

Answer 3

最快的方法：分而治之。

假设您的范围是0到MAX_int，那么您就有1到10位数字。您可以使用“分而治之”来接近此间隔，每个输入最多可进行4次比较。首先，用一个比较将[1.10]划分为[1.5]和[6.10]，然后使用一个比较将每个长度5间隔划分为1长度3和1长度2区间。长度2间隔需要再进行一次比较(总计3次比较)，长度3间隔可分为长度1间隔(解)和长度2间隔。所以，你需要3或4个比较。

没有除法，没有浮点运算，没有昂贵的对数，只有整数比较。

代码(长但快)：

if (n < 100000){
        // 5 or less
        if (n < 100){
            // 1 or 2
            if (n < 10)
                return 1;
            else
                return 2;
        }else{
            // 3 or 4 or 5
            if (n < 1000)
                return 3;
            else{
                // 4 or 5
                if (n < 10000)
                    return 4;
                else
                    return 5;
            }
        }
    } else {
        // 6 or more
        if (n < 10000000) {
            // 6 or 7
            if (n < 1000000)
                return 6;
            else
                return 7;
        } else {
            // 8 to 10
            if (n < 100000000)
                return 8;
            else {
                // 9 or 10
                if (n < 1000000000)
                    return 9;
                else
                    return 10;
            }
        }
    }

基准测试(JVM预热之后)-参见下面的代码，以了解基准测试是如何运行的：

1. 基线方法(有字符串长度)：2145 ms
2. log 10方法：711 ms=3.02倍于基线
3. 重复划分：2797 ms=0.77倍于基线
4. 分而治之：74ms=28.99

   
   

   比基线快几倍

完整代码：

public static void main(String[] args)throws Exception{

    // validate methods:
    for (int i = 0; i < 1000; i++)
        if (method1(i) != method2(i))
            System.out.println(i);
    for (int i = 0; i < 1000; i++)
        if (method1(i) != method3(i))
            System.out.println(i + " " + method1(i) + " " + method3(i));
    for (int i = 333; i < 2000000000; i += 1000)
        if (method1(i) != method3(i))
            System.out.println(i + " " + method1(i) + " " + method3(i));
    for (int i = 0; i < 1000; i++)
        if (method1(i) != method4(i))
            System.out.println(i + " " + method1(i) + " " + method4(i));
    for (int i = 333; i < 2000000000; i += 1000)
        if (method1(i) != method4(i))
            System.out.println(i + " " + method1(i) + " " + method4(i));

    // work-up the JVM - make sure everything will be run in hot-spot mode
    allMethod1();
    allMethod2();
    allMethod3();
    allMethod4();

    // run benchmark
    Chronometer c;

    c = new Chronometer(true);
    allMethod1();
    c.stop();
    long baseline = c.getValue();
    System.out.println(c);

    c = new Chronometer(true);
    allMethod2();
    c.stop();
    System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times faster than baseline");

    c = new Chronometer(true);
    allMethod3();
    c.stop();
    System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times faster than baseline");

    c = new Chronometer(true);
    allMethod4();
    c.stop();
    System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times faster than baseline");
    }private static int method1(int n){
    return Integer.toString(n).length();}private static int method2(int n){
    if (n == 0)
        return 1;
    return (int)(Math.log10(n) + 1);}private static int method3(int n){
    if (n == 0)
        return 1;
    int l;
    for (l = 0 ; n > 0 ;++l)
        n /= 10;
    return l;}private static int method4(int n){
    if (n < 100000)
    {
        // 5 or less
        if (n < 100)
        {
            // 1 or 2
            if (n < 10)
                return 1;
            else
                return 2;
        }
        else
        {
            // 3 or 4 or 5
            if (n < 1000)
                return 3;
            else
            {
                // 4 or 5
                if (n < 10000)
                    return 4;
                else
                    return 5;
            }
        }
    }
    else
    {
        // 6 or more
        if (n < 10000000)
        {
            // 6 or 7
            if (n < 1000000)
                return 6;
            else
                return 7;
        }
        else
        {
            // 8 to 10
            if (n < 100000000)
                return 8;
            else
            {
                // 9 or 10
                if (n < 1000000000)
                    return 9;
                else
                    return 10;
            }
        }
    }}private static int allMethod1(){
    int x = 0;
    for (int i = 0; i < 1000; i++)
        x = method1(i);
    for (int i = 1000; i < 100000; i += 10)
        x = method1(i);
    for (int i = 100000; i < 1000000; i += 100)
        x = method1(i);
    for (int i = 1000000; i < 2000000000; i += 200)
        x = method1(i);

    return x;}private static int allMethod2(){
    int x = 0;
    for (int i = 0; i < 1000; i++)
        x = method2(i);
    for (int i = 1000; i < 100000; i += 10)
        x = method2(i);
    for (int i = 100000; i < 1000000; i += 100)
        x = method2(i);
    for (int i = 1000000; i < 2000000000; i += 200)
        x = method2(i);

    return x;}private static int allMethod3(){
    int x = 0;
    for (int i = 0; i < 1000; i++)
        x = method3(i);
    for (int i = 1000; i < 100000; i += 10)
        x = method3(i);
    for (int i = 100000; i < 1000000; i += 100)
        x = method3(i);
    for (int i = 1000000; i < 2000000000; i += 200)
        x = method3(i);

    return x;}private static int allMethod4(){
    int x = 0;
    for (int i = 0; i < 1000; i++)
        x = method4(i);
    for (int i = 1000; i < 100000; i += 10)
        x = method4(i);
    for (int i = 100000; i < 1000000; i += 100)
        x = method4(i);
    for (int i = 1000000; i < 2000000000; i += 200)
        x = method4(i);

    return x;}

同样，基准：

1. 基线方法(有字符串长度)：2145 ms
2. log 10方法：711 ms=3.02倍于基线
3. 重复划分：2797 ms=0.77倍于基线
4. 分而治之：74ms=28.99

   
   

   比基线快几倍

编辑：在编写了基准测试之后，我从Java 6中偷偷地进入了Integer.toString，并发现它使用：

final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
                                  99999999, 999999999, Integer.MAX_VALUE };
                                  // Requires positive xstatic int stringSize(int x) {
    for (int i=0; ; i++)
        if (x <= sizeTable[i])
            return i+1;}

我将其与分而治之的解决方案相对照：

1. 分而治之：104 ms
2. Java 6解决方案-迭代和比较：406 ms

我的大约快4倍。