有没有比这个方法更简洁的方法来获取整数的位数?

int numDigits = String.valueOf(1000).length();

当前回答

我看到有人使用String库,甚至使用Integer类。这没什么问题,但是求位数的算法并不复杂。我在这个例子中使用的是long类型,但它也可以用于int类型。

 private static int getLength(long num) {

    int count = 1;

    while (num >= 10) {
        num = num / 10;
        count++;
    }

    return count;
}

其他回答

最快的方法:分而治之。

Assuming your range is 0 to MAX_INT, then you have 1 to 10 digits. You can approach this interval using divide and conquer, with up to 4 comparisons per each input. First, you divide [1..10] into [1..5] and [6..10] with one comparison, and then each length 5 interval you divide using one comparison into one length 3 and one length 2 interval. The length 2 interval requires one more comparison (total 3 comparisons), the length 3 interval can be divided into length 1 interval (solution) and a length 2 interval. So, you need 3 or 4 comparisons.

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

代码(长但快):

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预热之后)——查看下面的代码以了解基准测试是如何运行的:

基线方法(使用String.length): 2145毫秒 Log10方法:711ms = 3.02次 和基线一样快 重复除:2797ms = 0.77次 和基线一样快 分治: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 as fast as baseline");
    
    c = new Chronometer(true);
    allMethod3();
    c.stop();
    System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times as fast as baseline");
    
    c = new Chronometer(true);
    allMethod4();
    c.stop();
    System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times as fast as 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;
}

基准:

基线方法(String.length): 2145ms Log10方法:711ms =基线速度的3.02倍 重复除:2797ms =基线速度的0.77倍 分治:74毫秒= 28.99倍的基线速度


Edit

在我写完基准测试之后,我偷偷地看了一下Integer。toString来自Java 6,我发现它使用:

final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
                                  99999999, 999999999, Integer.MAX_VALUE };

// Requires positive x
static int stringSize(int x) {
    for (int i=0; ; i++)
        if (x <= sizeTable[i])
            return i+1;
}

我以我的分治方案为基准:

分治法:104毫秒 Java 6解决方案-迭代和比较:406ms

我的速度大约是Java 6解决方案的4倍。

用设计(基于问题)。这是分治法的另一种。我们将首先定义一个枚举(考虑到它仅用于unsigned int)。

public enum IntegerLength {
    One((byte)1,10),
    Two((byte)2,100),
    Three((byte)3,1000),
    Four((byte)4,10000),
    Five((byte)5,100000),
    Six((byte)6,1000000),
    Seven((byte)7,10000000),
    Eight((byte)8,100000000),
    Nine((byte)9,1000000000);

    byte length;
    int value;

    IntegerLength(byte len,int value) {
        this.length = len;
        this.value = value;
    }

    public byte getLenght() {
        return length;
    }

    public int getValue() {
        return value;
    }
}

现在我们将定义一个类,它遍历枚举的值,并比较并返回适当的长度。

public class IntegerLenght {
    public static byte calculateIntLenght(int num) {    
        for(IntegerLength v : IntegerLength.values()) {
            if(num < v.getValue()){
                return v.getLenght();
            }
        }
        return 0;
    }
}

此解决方案的运行时间与分治方法相同。

这个递归方法呢?

    private static int length = 0;

    public static int length(int n) {
    length++;
    if((n / 10) < 10) {
        length++;
    } else {
        length(n / 10);
    }
    return length;
}

我们可以使用递归循环来实现这一点

    public static int digitCount(int numberInput, int i) {
        while (numberInput > 0) {
        i++;
        numberInput = numberInput / 10;
        digitCount(numberInput, i);
        }
        return i;
    }

    public static void printString() {
        int numberInput = 1234567;
        int digitCount = digitCount(numberInput, 0);

        System.out.println("Count of digit in ["+numberInput+"] is ["+digitCount+"]");
    }

我还没有看到基于乘法的解决方案。对数、除法和基于字符串的解决方案将在数百万个测试用例中变得相当笨拙,所以这里有一个int型的解决方案:

/**
 * Returns the number of digits needed to represents an {@code int} value in 
 * the given radix, disregarding any sign.
 */
public static int len(int n, int radix) {
    radixCheck(radix); 
    // if you want to establish some limitation other than radix > 2
    n = Math.abs(n);

    int len = 1;
    long min = radix - 1;

    while (n > min) {
        n -= min;
        min *= radix;
        len++;
    }

    return len;
}

以10为基底,这是可行的,因为n本质上是与9,99,999…因为min是9,90,900…n被减去9,90,900…

不幸的是,仅仅因为溢出而替换int的每个实例是不能移植到long的。另一方面,它恰好适用于2垒和10垒(但对于大多数其他垒来说严重失败)。您将需要一个用于溢出点的查找表(或除法测试……)电子战)

/**
 * For radices 2 &le r &le Character.MAX_VALUE (36)
 */
private static long[] overflowpt = {-1, -1, 4611686018427387904L,
    8105110306037952534L, 3458764513820540928L, 5960464477539062500L,
    3948651115268014080L, 3351275184499704042L, 8070450532247928832L,
    1200757082375992968L, 9000000000000000000L, 5054470284992937710L,
    2033726847845400576L, 7984999310198158092L, 2022385242251558912L,
    6130514465332031250L, 1080863910568919040L, 2694045224950414864L,
    6371827248895377408L, 756953702320627062L, 1556480000000000000L,
    3089447554782389220L, 5939011215544737792L, 482121737504447062L,
    839967991029301248L, 1430511474609375000L, 2385723916542054400L,
    3902460517721977146L, 6269893157408735232L, 341614273439763212L,
    513726300000000000L, 762254306892144930L, 1116892707587883008L,
    1617347408439258144L, 2316231840055068672L, 3282671350683593750L,
    4606759634479349760L};

public static int len(long n, int radix) {
    radixCheck(radix);
    n = abs(n);

    int len = 1;
    long min = radix - 1;
    while (n > min) {
        len++;
        if (min == overflowpt[radix]) break;
        n -= min;
        min *= radix;

    }

    return len;
}