Как найти количество цифр в целом числе

Constant-cost version that uses x86 assembly and a lookup table:

int count_bsr(int i) {
    struct {
            int max;
            int count;
    } static digits[32] = {
            { 9, 1 }, { 9, 1 }, { 9, 1 }, { 9, 1 },
            { 99, 2 }, { 99, 2 }, { 99, 2 },
            { 999, 3 }, { 999, 3 }, { 999, 3 },
            { 9999, 4 }, { 9999, 4 }, { 9999, 4 }, { 9999, 4 },
            { 99999, 5 }, { 99999, 5 }, { 99999, 5 },
            { 999999, 6 }, { 999999, 6 }, { 999999, 6 },
            { 9999999, 7 }, { 9999999, 7 }, { 9999999, 7 }, { 9999999, 7 },
            { 99999999, 8 }, { 99999999, 8 }, { 99999999, 8 },
            { 999999999, 9 }, { 999999999, 9 }, { 999999999, 9 },
            { INT_MAX, 10 }, { INT_MAX, 10 }
    };
        register const int z = 0;
        register unsigned log2;
        if (i < 0) i = -i;
        __asm__ __volatile__ (
                "bsr %1, %0;"  
                "cmovz %2, %0;"
                : "=r" (log2)  
                : "rm" (i), "r"(z));
        return digits[log2].count + ( i > digits[log2].max );
}

Another one, with a smaller lookup table and a log10 approximation taken from here.

int count_bsr2( int i ) {
    static const unsigned limits[] =
            {0, 10, 100, 1000, 10000, 100000,
             1000000, 10000000, 100000000, 1000000000};
        register const int z = 0;
        register int l, log2;
        if (i < 0) i = -i;
        __asm__ __volatile__ (
                "bsr %1, %0;"  
                "cmovz %2, %0;"
                : "=r" (log2)  
                : "rm" (i), "r"(z));
       l = (log2 + 1) * 1233 >> 12;
       return (l + ((unsigned)i >= limits[l]));
}

Both of these take advantage of the fact that on x86 -INT_MIN is equal to INT_MIN.

Update:

As per suggestion here are the timings for the count_bsr and a slightly faster 64-bit only count_bsr_mod routines compared to the binary search and binary chop algos using very nice paxdiablo’s test program modified to generate sets with a random sign distribution. Tests were built with gcc 4.9.2 using “-O3 -falign-functions=16 -falign-jumps=16 -march=corei7-avx” options and executed on an otherwise quiescent Sandy Bridge system with turbo and sleep states off.

Time for               bsr mod:     270000  
Time for                   bsr:     340000  
Time for           binary chop:     800000  
Time for         binary search:     770000  
Time for     binary search mod:     470000  

Source for the test,

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <time.h>

#define numof(a) (sizeof(a) / sizeof(a[0]))

/* Random numbers and accuracy checks. */

static int rndnum[10000];
static int rt[numof(rndnum)];

/* All digit counting functions here. */

static int count_bchop (int n) {
    int r = 1;
    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
    if (n >= 100000000) {
        r += 8;
        n /= 100000000;
    }
    if (n >= 10000) {
        r += 4;
        n /= 10000;
    }
    if (n >= 100) {
        r += 2;
        n /= 100;
    }
    if (n >= 10)
        r++;

    return r;
}

static int count_bsearch(int i)
{
    if (i < 0)
    {
        if (i == INT_MIN)
            return 11; // special case for -2^31 because 2^31 can't fit in a two's complement 32-bit integer
        i = -i;
    }
    if              (i < 100000) {
        if          (i < 1000) {
            if      (i < 10)         return 1;
            else if (i < 100)        return 2;
            else                     return 3;
        } else {
            if      (i < 10000)      return 4;
            else                     return 5;
        }
    } else {
        if          (i < 10000000) {
            if      (i < 1000000)    return 6;
            else                     return 7;
        } else {
            if      (i < 100000000)  return 8;
            else if (i < 1000000000) return 9;
            else                     return 10;
        }
    }
}

// Integer log base 10, modified binary search.
static int count_bsearch_mod(int i) {
   unsigned x = (i >= 0) ? i : -i;
   if (x > 99)
      if (x > 999999)
         if (x > 99999999)
            return 9 + (x > 999999999);
         else
            return 7 + (x > 9999999);
      else
         if (x > 9999)
            return 5 + (x > 99999);
         else
            return 3 + (x > 999);
   else
         return 1 + (x > 9);
}

static int count_bsr_mod(int i) {
    struct {
            int m_count;
            int m_threshold;
    } static digits[32] =
    {
      { 1, 9 }, { 1, 9 }, { 1, 9 }, { 1, 9 },
      { 2, 99 }, { 2, 99 }, { 2, 99 },
      { 3, 999 }, { 3, 999 }, { 3, 999 },
      { 4, 9999 }, { 4, 9999 }, { 4, 9999 }, { 4, 9999 },
      { 5, 99999 }, { 5, 99999 }, { 5, 99999 },
      { 6, 999999 }, { 6, 999999 }, { 6, 999999 },
      { 7, 9999999 }, { 7, 9999999 }, { 7, 9999999 }, { 7, 9999999 },
      { 8, 99999999 }, { 8, 99999999 }, { 8, 99999999 },
      { 9, 999999999 }, { 9, 999999999 }, { 9, 999999999 },
      { 10, INT_MAX }, { 10, INT_MAX }
    };
        __asm__ __volatile__ (
            "cdq                    nt"
            "xorl %%edx, %0         nt"
            "subl %%edx, %0         nt"
            "movl %0, %%edx         nt"
            "bsrl %0, %0            nt"
            "shlq $32, %%rdx        nt"
            "movq %P1(,%q0,8), %q0  nt"
            "cmpq %q0, %%rdx        nt"
            "setg %%dl              nt"
            "addl %%edx, %0         nt"
                : "+a"(i)
                : "i"(digits)
                : "rdx", "cc"
        );
    return i;
}

static int count_bsr(int i) {
    struct {
            int max;
            int count;
    } static digits[32] = {
            { 9, 1 }, { 9, 1 }, { 9, 1 }, { 9, 1 },
            { 99, 2 }, { 99, 2 }, { 99, 2 },
            { 999, 3 }, { 999, 3 }, { 999, 3 },
            { 9999, 4 }, { 9999, 4 }, { 9999, 4 }, { 9999, 4 },
            { 99999, 5 }, { 99999, 5 }, { 99999, 5 },
            { 999999, 6 }, { 999999, 6 }, { 999999, 6 },
            { 9999999, 7 }, { 9999999, 7 }, { 9999999, 7 }, { 9999999, 7 },
            { 99999999, 8 }, { 99999999, 8 }, { 99999999, 8 },
            { 999999999, 9 }, { 999999999, 9 }, { 999999999, 9 },
            { INT_MAX, 10 }, { INT_MAX, 10 }
    };
        register const int z = 0;
        register unsigned log2;
        if (i < 0) i = -i;
        __asm__ __volatile__ (
                "bsr %1, %0;"  
                "cmovz %2, %0;"
                : "=r" (log2)  
                : "rm" (i), "r"(z));
        return digits[log2].count + ( i > digits[log2].max );
}

/* Structure to control calling of functions. */

typedef struct {
    int (*fnptr)(int);
    const char *desc;
} tFn;

static tFn fn[] = {
 {   NULL,                              NULL },
 {   count_bsr_mod,  "              bsr mod" },
 {   count_bsr,      "                  bsr" },
 {   count_bchop,    "          binary chop" },
 {   count_bsearch,  "        binary search" },
 {   count_bsearch_mod,"    binary search mod"}
};
static clock_t clk[numof (fn)];

int main (int c, char *v[]) {
    int i, j, k, r;
    int s = 1;

    /* Test code:
        printf ("%11d %dn", INT_MIN, count_bsearch(INT_MIN));
        //for (i = -1000000000; i != 0; i /= 10)
        for (i = -999999999; i != 0; i /= 10)
            printf ("%11d %dn", i, count_bsearch(i));
        printf ("%11d %dn", 0, count_bsearch(0));
        for (i = 1; i != 1000000000; i *= 10)
            printf ("%11d %dn", i, count_bsearch(i));
        printf ("%11d %dn", 1000000000, count_bsearch(1000000000));
        printf ("%11d %dn", INT_MAX, count_bsearch(INT_MAX));
    return 0;
    /* */

    /* Randomize and create random pool of numbers. */

    int p, n;
    p = n = 0;
    srand (time (NULL));
    for (j = 0; j < numof (rndnum); j++) {
        rndnum[j] = ((rand() & 2) - 1) * rand();
    }
    rndnum[0] = INT_MAX;
    rndnum[1] = INT_MIN;

    /* For testing. */
    for (k = 0; k < numof (rndnum); k++) {
        rt[k] = (fn[1].fnptr)(rndnum[k]);
    }

    /* Test each of the functions in turn. */

    clk[0] = clock();
    for (i = 1; i < numof (fn); i++) {
        for (j = 0; j < 10000; j++) {
            for (k = 0; k < numof (rndnum); k++) {
                r = (fn[i].fnptr)(rndnum[k]);
                /* Test code:
                    if (r != rt[k]) {
                        printf ("Mismatch error [%s] %d %d %d %dn",
                            fn[i].desc, k, rndnum[k], rt[k], r);
                        return 1;
                    }
                /* */
            }
        }
        clk[i] = clock();
    }

    /* Print out results. */

    for (i = 1; i < numof (fn); i++) {
        printf ("Time for %s: %10dn", fn[i].desc, (int)(clk[i] - clk[i-1]));
    }

    return 0;
}

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

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

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

Способ 1: Преобразование в строку и подсчет символов

Один из простейших способов подсчета цифр в числе в языке Python — это преобразовать число в строку и подсчитать количество символов в этой строке с помощью функции len(). Для этого необходимо использовать встроенную функцию str() для преобразования числа в строку. Затем с помощью функции len() можно получить количество символов в этой строке, что будет равно количеству цифр в числе. Этот способ не требует использования дополнительных модулей или библиотек, поэтому он достаточно прост в реализации. Однако он не является самым эффективным способом подсчета цифр в больших числах.

Приведём простой пример:

num = 12345
num_str = str(num)
count = len(num_str)
print("Количество цифр в числе", num, ":", count)

В этом примере мы преобразуем число num в строку num_str с помощью встроенной функции str(), а затем считаем количество символов в строке с помощью функции len(). Результат выводится с помощью функции print().

Предположим, что нам необходимо запросить число у пользователя. И так как мы сразу получаем от пользователя сразу строку, то наш код преобразуется следующим образом:

num_str = input("Введите число:")
count = len(num_str)
print("Количество цифр в числе", num_str, ":", count)

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

Поэтому нам нужно добавить вызов функции abs() для преобразования отрицательного числа в положительное перед началом подсчета. И вот что у нас получится:

num_str = input("Введите число:")
num = abs(int(num_str))
count = len(str(num))
print("Количество цифр в числе", num_str, ":", count)

В первой строке кода мы получаем от пользователя число в виде строки. Во второй строке сначала преобразовываем строку в число, а после вызываем функцию abs() . В третье строке считаем количество символов, не забыв при этом преобразовать число обратно в строку.

Способ 2: Использование цикла и операции целочисленного деления

Еще один способ подсчета количества цифр в числе — использование цикла и операции целочисленного деления. Этот метод заключается в том, чтобы повторять целочисленное деление числа на 10 до тех пор, пока оно не станет меньше 10. Каждый раз при целочисленном делении на 10 из числа удаляется одна цифра, и таким образом можно подсчитать количество цифр в числе. Этот подход основан на том факте, что при целочисленном делении числа на 10 результат будет равен числу, в котором отсутствует последняя цифра. Например, при целочисленном делении числа 123 на 10 получим 12.

В результате, чтобы использовать этот способ для подсчета количества цифр в числе, можно использовать цикл while, который будет продолжаться, пока число не станет меньше 10. При каждой итерации цикла мы будем  целочисленно делить число на 10, увеличивать счетчик цифр на 1 и повторять цикл до тех пор, пока число не станет меньше 10. Когда число меньше 10, добавляем 1 к счетчику и выходим из цикла.

Например, если у нас есть число 12345, мы можем использовать этот метод для подсчета количества цифр в числе следующим образом:

number = 12345
count = 0
while number > 0:
    count += 1
    number = number // 10

print("Количество цифр в числе:", count)

Если нам необходимо чтобы программа работала и с отрицательными числами, то нам также нужно добавить вызов функции abs() для преобразования отрицательного числа в положительное перед началом подсчета. Также добавим условие для 0, и получим следующий код:

num = -98765
count = 0
if num == 0:
    count = 1
else:
    num = abs(num)
    while num > 0:
        count += 1
        num //= 10

print("Количество цифр в числе:", count)

Способ 3: Использование рекурсии

Для подсчета количества цифр в числе можно использовать рекурсию. Рекурсия — это метод, при котором функция вызывает саму себя. В данном случае функция принимает число и сравнивает его с нулем. Если число равно нулю, то функция возвращает 0. Если число не равно нулю, то функция вызывает саму себя, передавая число, целочисленно деленное на 10, и увеличивает счетчик на 1. Рекурсивный вызов функции продолжается, пока число не станет равным 0. Затем функция возвращает счетчик — количество цифр в числе.

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

Пример рекурсивной функции для подсчета количества цифр в числе:

def count_digits(n):
    n = abs(n)  # преобразование отрицательного числа в положительное
    if n < 10:
        return 1
    else:
        return 1 + count_digits(n // 10)

Способ 4: Использование математических функций

Для подсчета количества цифр в числе можно использовать математические функции. Например, можно воспользоваться свойством логарифма, которое позволяет вычислить количество цифр в числе, используя десятичный логарифм. Для этого нужно взять логарифм числа по основанию 10 и добавить к результату 1. Полученное число и будет являться количеством цифр в исходном числе. Данный подход может оказаться полезным, когда требуется узнать количество цифр в очень больших числах, так как для работы с такими числами может потребоваться много времени и памяти.

Приведём пример:

import math

num = 12345
count = int(math.log10(num))+1

print("Количество цифр в числе", num, "равно", count)

В этом коде мы импортируем модуль math и используем функцию log10() для определения десятичного логарифма числа. Затем мы добавляем 1 к результату и приводим его к целочисленному типу, чтобы получить количество цифр в числе.