Как я определяю количество цифр целого числа в C?

    int n = 437788;
    int N = 1; 
    while (n /= 10) N++; 

if (x == MININT) return 10;  //  abs(MININT) is not defined
x = abs (x);
if (x<10) return 1;
if (x<100) return 2;
if (x<1000) return 3;
if (x<10000) return 4;
if (x<100000) return 5;
if (x<1000000) return 6;
if (x<10000000) return 7;
if (x<100000000) return 8;
if (x<1000000000) return 9;
return 10; //max len for 32-bit integers

Очень неэлегантно. Но быстрее всех остальных. Журналы целочисленного деления и FP обходятся дорого. Если производительность не является проблемой, я предпочитаю решение log10.

Из Bit Twiddling Hacks:

Найти целочисленную логарифмическую базу 10 целого числа очевидным способом

Обратите внимание на порядок сравнений в нем.

Вы можете: этаж (log10 (abs (x))) + 1 Или, если вы хотите сэкономить на циклах, вы можете просто выполнять сравнения

if(x<10)
  return 1;
if(x<100)
  return 2;
if(x<1000)
  return 3;
etc etc

. Это позволяет избежать любых дорогостоящих в вычислительном отношении функций, таких как журнал или даже умножение или деление. Хотя это неэлегантно, это можно скрыть, инкапсулируя его в функцию. Это не сложно или сложно поддерживать, поэтому я бы не отказался от этого подхода из-за плохой практики кодирования; Я чувствую, что это означало бы выбросить ребенка вместе с водой из ванны.

Делите на 10 в цикле, пока результат не достигнет нуля. Количество итераций будет соответствовать количеству десятичных цифр.

Предполагая, что вы ожидаете получить 0 цифр в нулевом значении:

int countDigits( int value )
{
    int result = 0;
    while( value != 0 ) {
       value /= 10;
       result++;
    }
    return result;
}

Псевдоалгоритм двоичного поиска, чтобы не получить цифры r в v ..

if (v < 0 ) v=-v;

r=1;

if (v >= 100000000)
{
  r+=8;
  v/=100000000;
}

if (v >= 10000) {
    r+=4;
    v/=10000;
}

if (v >= 100) {
    r+=2;
    v/=100;
}

if( v>=10)
{
    r+=1;
}

return r;

Рекурсивный подход: -)

int numPlaces (int n) {
    if (n < 0) return numPlaces ((n == INT_MIN) ? MAX_INT: -n);
    if (n < 10) return 1;
    return 1 + numPlaces (n / 10);
}

Или итеративный:

int numPlaces (int n) {
    int r = 1;
    if (n < 0) n = (n == INT_MIN) ? INT_MAX: -n;
    while (n > 9) {
        n /= 10;
        r++;
    }
    return r;
}

Или необработанная скорость:

int numPlaces (int n) {
    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
    if (n < 10) return 1;
    if (n < 100) return 2;
    if (n < 1000) return 3;
    if (n < 10000) return 4;
    if (n < 100000) return 5;
    if (n < 1000000) return 6;
    if (n < 10000000) return 7;
    if (n < 100000000) return 8;
    if (n < 1000000000) return 9;
    /*      2147483647 is 2^31-1 - add more ifs as needed
       and adjust this final return as well. */
    return 10;
}

Те выше были изменены, чтобы лучше обрабатывать MININT. В любых странных системах, которые не следуют разумным правилам дополнения 2 ⁿ two для целых чисел, они могут нуждаться в дальнейшей настройке.

Версия с необработанной скоростью фактически превосходит версию с плавающей запятой, модифицированную ниже:

int numPlaces (int n) {
    if (n == 0) return 1;
    return floor (log10 (abs (n))) + 1;
}

Проведя сто миллионов итераций, я получил следующие результаты:

Raw speed with 0:            0 seconds
Raw speed with 2^31-1:       1 second
Iterative with 2^31-1:       5 seconds
Recursive with 2^31-1:       6 seconds
Floating point with 1:       6 seconds
Floating point with 2^31-1:  7 seconds

Это на самом деле меня немного удивило - я думал, что чипы Intel имеют приличный FPU, но я полагаю, что общие операции FP по-прежнему не могут конкурировать с оптимизированным вручную целочисленным кодом.

Обновите следующие предложения stormsoul:

Тестирование многократно-итеративного решения с помощью stormsoul дает результат в 4 секунды, так что пока оно ' намного быстрее, чем решение с итеративным делением, оно по-прежнему не соответствует оптимизированному решению оператора if.

Выбор аргументов из пула 1000 случайно сгенерированных чисел увеличил время ожидания исходной скорости до 2 секунд, поэтому, пока Похоже, что использование одного и того же аргумента каждый раз могло иметь некоторое преимущество, это все еще самый быстрый из перечисленных подходов.

Компиляция с -O2 улучшила скорость, но не относительное положение (я увеличил количество итераций в десять раз, чтобы проверить это).

Любой дальнейший анализ должен будет серьезно затронуть внутренние механизмы эффективности ЦП (различные типы оптимизации, использование кешей, прогноз ветвления, какой у вас процессор, температура окружающей среды в комнате и т. on), что будет мешать моей оплачиваемой работе :-). Это было интересное развлечение, но, в какой-то момент окупаемость инвестиций в оптимизацию становится слишком маленькой, чтобы иметь значение. Я думаю, что у нас есть достаточно решений, чтобы ответить на вопрос (который, в конце концов, не касался скорости).

Дальнейшее обновление:

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

Делайте с ним, как хотите:

#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_recur (int n) {
    if (n < 0) return count_recur ((n == INT_MIN) ? INT_MAX : -n);
    if (n < 10) return 1;
    return 1 + count_recur (n / 10);
}

static int count_diviter (int n) {
    int r = 1;
    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
    while (n > 9) {
        n /= 10;
        r++;
    }
    return r;
}

static int count_multiter (int n) {
    unsigned int num = abs(n);
    unsigned int x, i;
    for (x=10, i=1; ; x*=10, i++) {
        if (num < x)
            return i;
        if (x > INT_MAX/10)
            return i+1;
    }
}

static int count_ifs (int n) {
    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
    if (n < 10) return 1;
    if (n < 100) return 2;
    if (n < 1000) return 3;
    if (n < 10000) return 4;
    if (n < 100000) return 5;
    if (n < 1000000) return 6;
    if (n < 10000000) return 7;
    if (n < 100000000) return 8;
    if (n < 1000000000) return 9;
    /*      2147483647 is 2^31-1 - add more ifs as needed
    and adjust this final return as well. */
    return 10;
}

static int count_revifs (int n) {
    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
    if (n > 999999999) return 10;
    if (n > 99999999) return 9;
    if (n > 9999999) return 8;
    if (n > 999999) return 7;
    if (n > 99999) return 6;
    if (n > 9999) return 5;
    if (n > 999) return 4;
    if (n > 99) return 3;
    if (n > 9) return 2;
    return 1;
}

static int count_log10 (int n) {
    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
    if (n == 0) return 1;
    return floor (log10 (n)) + 1;
}

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;
}

/* Structure to control calling of functions. */

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

static tFn fn[] = {
    NULL,                              NULL,
    count_recur,    "            recursive",
    count_diviter,  "     divide-iterative",
    count_multiter, "   multiply-iterative",
    count_ifs,      "        if-statements",
    count_revifs,   "reverse-if-statements",
    count_log10,    "               log-10",
    count_bchop,    "          binary chop",
};
static clock_t clk[numof (fn)];

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

    /* Test code:
        printf ("%11d %d\n", INT_MIN, count_recur(INT_MIN));
        for (i = -1000000000; i != 0; i /= 10)
            printf ("%11d %d\n", i, count_recur(i));
        printf ("%11d %d\n", 0, count_recur(0));
        for (i = 1; i != 1000000000; i *= 10)
            printf ("%11d %d\n", i, count_recur(i));
        printf ("%11d %d\n", 1000000000, count_recur(1000000000));
        printf ("%11d %d\n", INT_MAX, count_recur(INT_MAX));
    /* */

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

    srand (time (NULL));
    for (j = 0; j < numof (rndnum); j++) {
        rndnum[j] = s * rand();
        s = -s;
    }
    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 %d\n",
                            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: %10d\n", fn[i].desc, (int)(clk[i] - clk[i-1]));
    }

    return 0;
}

Помните, что вам нужно убедиться, что вы используете правильную командную строку для его компиляции. В частности, вам может потребоваться явный список математической библиотеки, чтобы log10 () работал. Командная строка, которую я использовал в Debian, была gcc -o testprog testprog.c -lm .

И, с точки зрения результатов, вот таблица лидеров для моей среды :

Уровень оптимизации 0:

Time for reverse-if-statements:       1704
Time for         if-statements:       2296
Time for           binary chop:       2515
Time for    multiply-iterative:       5141
Time for      divide-iterative:       7375
Time for             recursive:      10469
Time for                log-10:      26953

Уровень оптимизации 3:

Time for         if-statements:       1047
Time for           binary chop:       1156
Time for reverse-if-statements:       1500
Time for    multiply-iterative:       2937
Time for      divide-iterative:       5391
Time for             recursive:       8875
Time for                log-10:      25438

НЕ используйте пол (log10 (...)). Это функции с плавающей запятой, причем медленные, чтобы добавить. Я считаю, что самым быстрым способом была бы эта функция:

int ilog10(int num)
{
   unsigned int num = abs(num);
   unsigned int x, i;
   for(x=10, i=1; ; x*=10, i++)
   {
      if(num < x)
         return i;
      if(x > INT_MAX/10)
         return i+1;
   }
}

Обратите внимание, что версия двоичного поиска, которую предлагали некоторые люди, могла быть медленнее из-за неверных предсказаний ветвления.

РЕДАКТИРОВАТЬ:

Я провел некоторое тестирование и получил действительно интересные результаты. Я рассчитал свою функцию вместе со всеми функциями, протестированными Pax, И функцией двоичного поиска, предоставленной lakshmanaraj. Тестирование выполняется с помощью следующего фрагмента кода:

start = clock();
for(int i=0; i<10000; i++)
   for(int j=0; j<10000; j++)
      tested_func(numbers[j]);
end = clock();
tested_func_times[pass] = end-start;

Где массив чисел [] содержит случайно сгенерированные числа по всему диапазону типа int (за исключением MIN_INT). Тестирование повторялось для каждой тестируемой функции на ОДНОМ Массиве чисел []. Весь тест проводился 10 раз, результаты усреднялись по всем проходам. Код был скомпилирован с помощью GCC 4.3.2 с уровнем оптимизации -O3.

Вот результаты:

floating-point log10:     10340ms
recursive divide:         3391ms
iterative divide:         2289ms
iterative multiplication: 1071ms
unrolled tests:           859ms
binary search:            539ms

Должен сказать, я был очень удивлен. Бинарный поиск оказался намного лучше, чем я ожидал. Я проверил, как GCC скомпилировал этот код в asm. О_О. Теперь ЭТО впечатляет. Он был оптимизирован намного лучше, чем я думал, благодаря очень хитрым способам избежать большинства веток. Неудивительно, что это БЫСТРО.