Способ получить количество цифр в INT?

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 делите, используя одно сравнение на один интервал длины 3 и один интервал длины 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. базовый метод (с длиной строки): 2145ms
2. log10 метод: 711мс = 3,02 раза быстрее базовой линии
3. повторное деление: 2797мс = 0,77 раза быстрее базовой линии
4. разделяй и властвуй: 74мс = 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. базовый метод (с длиной строки): 2145ms
2. log10 метод: 711мс = 3,02 раза быстрее базовой линии
3. повторное деление: 2797мс = 0,77 раза быстрее базовой линии
4. разделяй и властвуй: 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;
}

Я сравнил его с моим решением «разделяй и властвуй»:

4. разделяй и властвуй: 104мс
5. Решение Java 6 - итерация и сравнение: 406 мс

Мой примерно в 4 раза быстрее.

Answer 4

Два комментария к вашему бенчмарку: Java - это сложная среда, которая включает в себя своевременную компиляцию, сборку мусора и так далее, поэтому, чтобы получить справедливое сравнение, всякий раз, когда я запускаю бенчмарк, я всегда: (a) заключаю два теста в цикле, который запускает их в последовательности 5 или 10 раз. Довольно часто время выполнения на втором проходе цикла сильно отличается от первого. И (б) После каждого «подхода» я делаю System.gc (), чтобы попытаться запустить сборку мусора. В противном случае первый подход может сгенерировать кучу объектов, но этого недостаточно, чтобы вызвать сборку мусора, затем второй подход создает несколько объектов, куча исчерпывается и выполняется сбор мусора. Затем второй подход «взимается» за сбор мусора, оставленного первым подходом. Очень несправедливо!

Тем не менее, ни один из вышеперечисленных не имеет существенного значения в этом примере.

С этими модификациями или без них я получил совсем другие результаты, чем вы. Когда я запустил это, да, подход toString дал время выполнения от 6400 до 6600 миллисекунд, в то время как подход с логарифмированием составил от 20 000 до 20 400 миллисекунд. Вместо того, чтобы быть немного быстрее, лог-подход был для меня в 3 раза медленнее.

Обратите внимание, что эти два подхода сопряжены с очень разными затратами, поэтому это не является шокирующим: подход toString создаст много временных объектов, которые необходимо очистить, в то время как метод журналирования требует более интенсивных вычислений. Так что, возможно, разница в том, что на машине с меньшим объемом памяти toString требует большего количества циклов сборки мусора, в то время как на машине с более медленным процессором дополнительное вычисление журнала будет более болезненным.

Я также попробовал третий подход. Я написал эту маленькую функцию:

static int numlength(int n)
{
    if (n == 0) return 1;
    int l;
    n=Math.abs(n);
    for (l=0;n>0;++l)
        n/=10;
    return l;           
}

Это длилось от 1600 до 1900 миллисекунд - менее 1/3 от подхода toString и 1/10 от лог-подхода на моей машине.

Если бы у вас был широкий диапазон чисел, вы могли бы ускорить его, начав делить на 1 000 или 1 000 000, чтобы уменьшить количество циклов. Я не играл с этим.

Answer 5

Использование Java

int nDigits = Math.floor(Math.log10(Math.abs(the_integer))) + 1;

используйте import java.lang.Math.*; в начале

Использование C

int nDigits = floor(log10(abs(the_integer))) + 1;

использовать inclue math.h в начале

Answer 6

Поскольку число цифр в базе 10 целого числа равно 1 + усечение (log10 (число)) , вы можете сделать:

public class Test {

    public static void main(String[] args) {

        final int number = 1234;
        final int digits = 1 + (int)Math.floor(Math.log10(number));

        System.out.println(digits);
    }
}

Отредактировано , потому что мое последнее редактирование исправило пример кода, но не описание.

Answer 7

Пока не могу оставить комментарий, поэтому выложу отдельным ответом.

Логарифмическое решение не вычисляет правильное количество цифр для очень больших длинных целых чисел, например:

long n = 99999999999999999L;

// correct answer: 17
int numberOfDigits = String.valueOf(n).length();

// incorrect answer: 18
int wrongNumberOfDigits = (int) (Math.log10(n) + 1); 

Логарифмическое решение вычисляет неверное количество цифр в больших целых числах

Answer 8

Решение Мариана адаптировано для длинных чисел (до 9,223,372,036,854,775,807), на случай, если кто-то захочет скопировать и вставить его. В программе, которую я написал, для чисел до 10000 было гораздо более вероятным, поэтому я сделал для них специальную ветку. В любом случае, это не будет иметь существенного значения.

public static int numberOfDigits (long n) {     
    // Guessing 4 digit numbers will be more probable.
    // They are set in the first branch.
    if (n < 10000L) { // from 1 to 4
        if (n < 100L) { // 1 or 2
            if (n < 10L) {
                return 1;
            } else {
                return 2;
            }
        } else { // 3 or 4
            if (n < 1000L) {
                return 3;
            } else {
                return 4;
            }
        }           
    } else  { // from 5 a 20 (albeit longs can't have more than 18 or 19)
        if (n < 1000000000000L) { // from 5 to 12
            if (n < 100000000L) { // from 5 to 8
                if (n < 1000000L) { // 5 or 6
                    if (n < 100000L) {
                        return 5;
                    } else {
                        return 6;
                    }
                } else { // 7 u 8
                    if (n < 10000000L) {
                        return 7;
                    } else {
                        return 8;
                    }
                }
            } else { // from 9 to 12
                if (n < 10000000000L) { // 9 or 10
                    if (n < 1000000000L) {
                        return 9;
                    } else {
                        return 10;
                    }
                } else { // 11 or 12
                    if (n < 100000000000L) {
                        return 11;
                    } else {
                        return 12;
                    }
                }
            }
        } else { // from 13 to ... (18 or 20)
            if (n < 10000000000000000L) { // from 13 to 16
                if (n < 100000000000000L) { // 13 or 14
                    if (n < 10000000000000L) { 
                        return 13;
                    } else {
                        return 14;
                    }
                } else { // 15 or 16
                    if (n < 1000000000000000L) {
                        return 15;
                    } else {
                        return 16;
                    }
                }
            } else { // from 17 to ...¿20?
                if (n < 1000000000000000000L) { // 17 or 18
                    if (n < 100000000000000000L) {
                        return 17;
                    } else {
                        return 18;
                    }
                } else { // 19? Can it be?
                    // 10000000000000000000L is'nt a valid long.
                    return 19;
                }
            }
        }
    }
}

Answer 9

Как насчет простой старой математики?Делите на 10, пока не достигнете 0.

public static int getSize(long number) {
        int count = 0;
        while (number > 0) {
            count += 1;
            number = (number / 10);
        }
        return count;
    }

Answer 10

Могу ли я попробовать? ;)

на основе решения Дирка

final int digits = number==0?1:(1 + (int)Math.floor(Math.log10(Math.abs(number))));