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

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

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 (наихудший результат)

Комментарии 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
                                Если брать целочисленый логарифм, то ничего не получится, так как потеряная дробная часть будет вносить ошибку. А вариант с плавающей точкой фактически эквивалентен тому, чтобы сразу взять десятичный логарифм.

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

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