Регистрация
21 октября 2015 в 12:46

Способы найти количество цифр в числе

С большой вероятностью можно предположить, что у каждого программиста была хоть раз такая задача. Есть много способов для нахождения количества цифр. В статье будут представлены несколько функций от самых банальных, и не очень.

1. Длина строки

Довольно банальный способ — это нахождения длинны строки. Это не самый быстрый способ, но для очень простых задач подходит. 

    public int getCountsOfDigits(long number) {
        return String.valueOf(Math.abs(number)).length();
    }

2. Цикл с делением

Распространённый способ, скорость которого линейно зависит от длины числа.

    public int getCountsOfDigits(long number) {
        int count = (number == 0) ? 1 : 0;
        while (number != 0) {
            count++;
            number /= 10;
        }
        return count;
    }


3. Десятичный логарифм и округление

Логарифм работает за константное время, преимущество которого на больших числах. 

public static int getCountsOfDigits(long number) {
   return(number == 0) ? 1 : (int) Math.ceil(Math.log10(Math.abs(number) + 0.5));
  }

Можно использовать не только Math.ceil это лишь один из вариантов использования логарифма.

4. Сравнение

Быстрый, но не практичный способ из-за количества кода только для int ушло 38 строк. Конечно найдутся умельцы, которые смогут сделать красивее, и понятней. Не буду оставлять код для long, а оставлю для int, но думаю принцип ясен.

Код
    public static int getCountsOfDigits(int n) {
        if (n < 100000) {
            if (n < 100) {
                if (n < 10) {
                    return 1;
                } else {
                    return 2;
                }
            } else {
                if (n < 1000) {
                    return 3;
                } else {
                    if (n < 10000) {
                        return 4;
                    } else {
                        return 5;
                    }
                }
            }
        } else {
            if (n < 10000000) {
                if (n < 1000000) {
                    return 6;
                } else {
                    return 7;
                }
            } else {
                if (n < 100000000) {
                    return 8;
                } else {
                    if (n < 1000000000) {
                        return 9;
                    } else {
                        return 10;
                    }
                }
            }
        }
    }


Рейтинг выглядит так:
1. Сравнения (показывают лучший результат)
2. Логарифм
3. Деление
4. String (наихудший результат)
Теги:
Хабы:
Реклама
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее

Похожие публикации

Вакансии

Больше вакансий на Хабр Карьере
Реклама
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее

Комментарии 41

    +4
    В JDK такой способ:

    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;
}
      +6
      А для long — такой:
      // Requires positive x
static int stringSize(long x) {
    long p = 10;
    for (int i=1; i<19; i++) {
        if (x < p)
            return i;
        p = 10*p;
    }
    return 19;
}


      Заметьте, что можно изящно заменить деление умножением, которое работает быстрее.
        –6
        заменить деление умножением, которое работает быстрее

        Для целых чисел разве есть разница в скорости? Ведь и та и другая команда процессора выполняется за 1 такт.
          +5
          Да, есть. В современных процессорах много чего выполняется быстрее, чем за такт.
            –1
            Если вы в курсе, то поясните насколько целочисленное (не с плавающей точкой) умножение выполняется быстрее деления.

            На практике проверил несколько тестов — разницы не выявил.

            В сети нашел данные: IDIV выполняется за время от от14 до 41 тактов, IMUL за время от от 9 до 41. Но это данные для Intel 80386. Но для этого процессора еще был математический сопроцессор (отдельно).

            Интересуют не предрассудки, основаные на временах Intel 80386, а реальное положение дел.
              0
              На практике проверил несколько тестов — разницы не выявил.

              Как проверяли? Деление на константу компиляторы заменяют умножением и сдвигом, habrahabr.ru/post/256827
            0
            Ведь и та и другая команда процессора выполняется за 1 такт.
            С чего вы взяли? В современных процессорах отношение «скорости» к кол-ву тактов, конечно, весьма условно, но само по себе деление выполняется за несколько десятков тактов, емнип.
              0
              С чего вы взяли?

              На счет 1 такта, действительно ошибся.

              себе деление выполняется за несколько десятков тактов

              Точных данных для современных процессоров не нашел. Для 80386 от 14 до 41, и от 9 до 41 тактов на деление и умножение соответственно.

              Думаю что разница если и есть, то на тестах она будет практически не заметна (для целых чисел).

              По этому нужно делать выбор в пользу более понятного кода.
                0
                На 100 млн. раз разница более 1 секунды (C#, 3.00 ГГц). Для разовых действий роли не играет, но в движке базы данных или в обсчете статистики будет заметно.

                // int a = 12345678, b = 10;
// int count = 100000000;

a / b: 00:00:01.7970217
a * b: 00:00:00.3328430
empty: 00:00:00.2414149

                Скрытый текст
                namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = 12345678, b = 10;
            int count = 100000000;

            Stopwatch sw;
            TimeSpan elapsed;



            sw = new Stopwatch();
            sw.Start();

            for (int i = 0; i < count; i++)
            {
                int x = a / b;
            }

            sw.Stop();
            elapsed = sw.Elapsed;

            Console.WriteLine(elapsed.ToString());



            sw = new Stopwatch();
            sw.Start();

            for (int i = 0; i < count; i++)
            {
                int x = a * b;
            }

            sw.Stop();
            elapsed = sw.Elapsed;

            Console.WriteLine(elapsed.ToString());



            sw = new Stopwatch();
            sw.Start();

            for (int i = 0; i < count; i++)
            {}

            sw.Stop();
            elapsed = sw.Elapsed;

            Console.WriteLine(elapsed.ToString());
        }
    }
}

                  0
                  Ваш тест у меня дает такой результат:

                  a / b: 00:00:00.5373696
                  a * b: 00:00:00.4528938
                  00:00:00.4440999

                  Если поменять местами блок умножения и деления:

                  a * b: 00:00:00.4561308
                  a / b: 00:00:00.4959119
                  00:00:00.4439775

                  Добавил в код накопитель результата (для предотвращения оптимизации) и увеличил count до 1000000000.

                  Получил такие данные:

                  00:00:05.0382424
                  00:00:06.9657105
                  00:00:04.4456098

                  Получается умножение работает быстрее на 28%, т.е. не в разы. Процессор Core i3 2.5 ГГц.
                    0
                    Ок, мне стало интересно, и я решил вернуться к тому, с чего все началось — к определению длины числа. Способ с делением во всех случаях медленнее умножения. Число 12345678, 20 млн. раз.

                    Debug, оптимизация отключена
a * b: 00:00:00.6641369
a / b: 00:00:02.0418462
empty: 00:00:00.0883897


Debug, оптимизация включена
a * b: 00:00:00.2367661
a / b: 00:00:01.5960753
empty: 00:00:00.0660346


Release, оптимизация отключена
a * b: 00:00:00.2784811
a / b: 00:00:01.8224548
empty: 00:00:00.0714300


Release, оптимизация включена
a * b: 00:00:00.2012901
a / b: 00:00:01.5951311
empty: 00:00:00.0554228

                    Скрытый текст
                    namespace test
{
    class Program
    {
        static uint getCount_Mul(uint x)
        {
            uint p = 10;
            uint count = 1;
            while (x >= p)
            {
                count++;
                p *= 10;
            }
            return count;
        }

        static uint getCount_Div(uint number)
        {
            uint count = (number == 0) ? (uint)1 : (uint)0;
            while (number > 0)
            {
                count++;
                number /= 10;
            }
            return count;
        }

        static void Main(string[] args)
        {
            uint a = 12345678;
            uint loopCount = 20000000;
            uint res = 0;

            Stopwatch sw;
            TimeSpan elapsed;



            Thread.Sleep(100);
            sw = new Stopwatch();
            sw.Start();

            for (int i = 0; i < loopCount; i++)
            {
                res += getCount_Mul(a);
            }

            sw.Stop();
            elapsed = sw.Elapsed;

            Console.WriteLine("a * b: " + elapsed.ToString());



            Thread.Sleep(100);
            sw = new Stopwatch();
            sw.Start();

            for (int i = 0; i < loopCount; i++)
            {
                res += getCount_Div(a);
            }

            sw.Stop();
            elapsed = sw.Elapsed;

            Console.WriteLine("a / b: " + elapsed.ToString());



            Thread.Sleep(100);
            sw = new Stopwatch();
            sw.Start();

            for (int i = 0; i < loopCount; i++)
            { }

            sw.Stop();
            elapsed = sw.Elapsed;

            Console.WriteLine("empty: " + elapsed.ToString());


            Console.WriteLine("res:   " + res);
        }
    }
}

                      0
                      На Core i7 разница в 4.4 раза (кстати неплохо бы отношение выводить тоже):
                      a * b: 00:00:00.1260080
a / b: 00:00:00.5574522
empty: 00:00:00.0106549
res:   320000000
          0
          Использование логарифма — не самая лучшая идея с точки зрения производительности для такой задачи.
            –1
            Если честно, не понял, почему длина строки — хуже всего :(
              0
              По скорости.
                –1
                Не «по чему», а «почему».
                Почему операция «длина строки» занимает больше времени, чем например, деление или логарифм.
                Про сравнение не спрашиваю. Ответ очевиден.
                  +1
                  Это все то же деление только еще добавляется деление по модулю, чтобы цифру получить, и затем копирование цифры в строку.
                    –1
                    Я был уверен, что после преобразования числа в строку будет хранится и длина строки — останется только получить это значение. Спасибо
                      +2
                      Вы не поняли. Проблема не в том, чтобы получить длину строки — она-то хранится отдельно, числом. Проблема в преобразовании числа в строку. Его надо распарсить, выделить память под массив символов и тд. Основное время тратится именно на это.
                        0
                        Действительно не понял. Теперь всё точно встало на своим места. Спасибо, Денис, что разжевали.
                          0
                          При этом для того, чтобы определить, сколько памяти выделить под массив символов, в самом начале вызывается один из методов, что я привёл выше.
                            0
                            С чего вы это взяли? Это адовые детали реализации.
                            int bufLen = 11; // Max number of chars in result
char[] buf = (sb != null) ? BUFFER.get() : new char[bufLen];
                              0
                              Где вы это взяли? Здесь смотрите.
                                0
                                Этим вы подтвердили мой тезис о деталях реализации. Мой кусок кода — из андроида.
                                  0
                                  Я не говорил, что такое поведение специфицировано. Ну по тормознутости андроидовской джавы кто только не проходился.
                                    0
                                    Вы указали способ определения длины строки в этом комменте. Я указал кусок кода, где это не так, а вы мне — где это так. И после этого утверждаете, что не говорили о том, что это специфицировано.
                                    Ну по тормознутости андроидовской джавы кто только не проходился.
                                    Это вообще не в тему. Мы тут вроде не бенчмарками разных реализаций джавы занимаемся.
                                      –1
                                      Вы указали способ определения длины строки в этом комменте. Я указал кусок кода, где это не так, а вы мне — где это так. И после этого утверждаете, что не говорили о том, что это специфицировано.
                                      Всё верно. Всё так и было. Не вижу противоречий.
                          0
                          Мало того что память выделить, так ещё попутно воспользоваться алгоритмом деления представленным выше (там использовать остальные прям без вариантов), к полученному добавлять на каждом шаге аски код нуля и вот это уже писать в массив.
                            0
                            Я бы советовал почитать джавовские исходники преобразования инта в строку. Не буду копипастить сюда все 68 строк метода, но, например, там есть такой цикл
                            // Calculate digits two-at-a-time till remaining digits fit in 16 bits
        while (i >= (1 << 16)) {
            // Compute q = n/100 and r = n % 100 as per "Hacker's Delight" 10-8
            int q = (int) ((0x51EB851FL * i) >>> 37);
            int r = i - 100*q;
            buf[--cursor] = ONES[r];
            buf[--cursor] = TENS[r];
            i = q;
        }
                              0
                              Насколько я понимаю, такой изыск сейчас излишен: даже в Java-7 его способен сделать сам JIT-компилятор. Поэтому смело пишите /100.
                0
                Есть ещё вот такой способ

                некрасиво, но максимально быстро:
                public static int NumLeadingZeroes(int x)
{
    int y, m, n;

    y = -(x >> 16);
    m = (y >> 16) & 16;
    n = 16 - m;
    x >>= m;
    y = x - 0x100;
    m = (y >> 16) & 8;
    n += m;
    x <<= m;
    y = x - 0x1000;
    m = (y >> 16) & 4;
    n += m;
    x <<= m;
    y = x - 0x4000;
    m = (y >> 16) & 2;
    n += m;
    x <<= m;
    y = x >> 14;
    m = y & ~(y >> 1);
    return n + 2 - m;
}

private static int[] _binaryApproximation = {
    9, 9, 9, 8, 8, 8,
    7, 7, 7, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3, 3,
    2, 2, 2, 1, 1, 1, 0, 0, 0, 0
};

private static int[] _fixApproximation = {
    1, 10, 100, 1000, 10000,
    100000, 1000000, 10000000, 100000000, 1000000000
};

public static int IntLog10(int x)
{
    int y;

    y = _binaryApproximation[NumLeadingZeroes(x)];
    if (x < _fixApproximation[y])
    {
        y = y - 1;
    }
    return y;
}

public static int DigitsCount(int x)
{
    return IntLog10(x) + 1;
}


                Сперва за константное время, без ветвлений, считаем число ведущих нулей в двоичной записи числа, по таблице находим аппроксимацию, при необходимости за один if её уточняем.

                Если действительно нужна скорость — прячем в либу (написанную на C/C++), высовываем наружу только интерфейс DigitsCount и радуемся. Но в 99.999% случаев хватает подсчёта числа символов в строке :)
                Хотя в реальном
                  +1
                  «Константное время», «без ветвлений», а сами заняли минимум три кэш-линии (а скорее четыре) в L1. Вы можете хвастаться скоростью в изолированном бенчмарке, не подозревая, что увеличили рабочий набор, оставив меньше места в кэше для данных самого приложения и увеличили вероятность кэш-миссов. «Максимально быстро» — понятие очень и очень относительное.

                  Либа, написанная на С/С++ выдаст существенный провал в скорости из-за переключения в нейтив. Алгоритмический Java-код часто JIT-ится не хуже, чем скомпилировался бы C/C++. Самое быстрое — это интринсик наколбасить на IR прямо внутри виртуальной машины =)
                • НЛО прилетело и опубликовало эту надпись здесь
                    0
                    Если читаемо, то скорее уже так:
                    public static int GetCountsOfDigits(int n)
{
    return n < 10 ? 1 :
        n < 100 ? 2 :
        n < 1000 ? 3 :
        n < 10000 ? 4 : 
        n < 100000 ? 5 :
        n < 1000000 ? 6 :
        n < 10000000 ? 7 :
        n < 100000000 ? 8 :
        n < 1000000000 ? 9 : 10;
}
                    +1
                    Может все таки поделитесь кодом как Вы измеряли скорость и что показали замеры в числах? Пока выглядит очень голословно.

                    И по сути заметки: первый же результат в гугле выдал ответ на stackoverflow, с которым я полностью солидарен. В 99% случаев String.valueOf подойдет на ура.
                      +2
                      Рейтинг выглядит так:
                      1. Сравнения (показывают лучший результат)
                      2. Логарифм
                      3. Деление
                      4. String (наихудший результат)

                      Рейтинг чего? По какому критерию оценивается? По скорости? У вас расчёт этой величины оказался узким горлышком, или вы от делать нечего решили соптимизировать что-нибудь?

                      String (или String.valueOf, упомянутый DigitalSmile) даёт наилучший результат с точки зрения читаемости. Иного здесь скорее всего и не требуется. Слабо верится, что производительность может упереться в подобную функцию.

                      Пример по «Сравнению» ничерта не читаем. Как следствие — не поддерживаем. А ещё у вас молоко убежало не учтены отрицательные значения. Вот менее страшная, но всё равно никуда не годная версия: gist.github.com/JIghtuse/012f2f6989a47a903727.
                      • НЛО прилетело и опубликовало эту надпись здесь
                          0
                          С битовыми операциями никто не искал решения?
                            0
                            Битовые операции хороши при работе в двоичной, восьмеричной и шестнадцатеричной системах счисления. В десятичной системе от них мало толку. Можно получить разве только первое приближение, которое впоследствии улучшать другими методами.
                              0
                              Насколько помню Log10(x)/Log2(x) = const. Так что можно найти в двоичной системе исчисления, и домножить на константу (предварительно её вычислив).
                                +1
                                Если брать целочисленый логарифм, то ничего не получится, так как потеряная дробная часть будет вносить ошибку. А вариант с плавающей точкой фактически эквивалентен тому, чтобы сразу взять десятичный логарифм.

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                          Что обсуждают

                          Самое читаемое

                          Ваш аккаунт

                          Разделы

                          Информация

                          Услуги

                          © 2006 – 2021 «Habr»
                          Настройка языка
                          О сайте
                          Служба поддержки
                          Мобильная версия