Как определить количество цифр целого числа в C?
Например,
n = 3432, result 4
n = 45, result 2
n = 33215, result 5
n = -357, result 3
Я думаю, я мог бы просто превратить его в строку, а затем получить длину строки, но это кажется запутанным и хакерским.
22 ответа
floor (log10 (abs (x))) + 1
Рекурсивный подход:-)
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. В любых странных системах, которые не следуют разумным правилам дополнения 2n два для целых чисел, они могут нуждаться в дальнейшей корректировке.
Необработанная скоростная версия фактически превосходит версию с плавающей запятой, измененную ниже:
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-Statement.
Выбор аргументов из пула из 1000 случайно сгенерированных чисел увеличил общее время до 2 секунд, поэтому, несмотря на то, что, возможно, было какое-то преимущество иметь один и тот же аргумент каждый раз, это по-прежнему самый быстрый подход в списке.
Компиляция с -O2 улучшила скорость, но не относительные позиции (я увеличил число итераций в десять раз, чтобы проверить это).
Любой дальнейший анализ должен серьезно затронуть внутреннюю работу эффективности ЦП (различные типы оптимизации, использование кэшей, прогнозирование ветвлений, какой у вас процессор на самом деле, температуру окружающей среды в помещении и т. Д.), Которая будет помешать моей оплачиваемой работе:-). Это было интересное развлечение, но в какой-то момент отдача от инвестиций для оптимизации становится слишком маленькой, чтобы иметь значение. Я думаю, что у нас есть достаточно решений, чтобы ответить на вопрос (который был, в конце концов, не о скорости).
Дальнейшее обновление:
Это будет мое последнее обновление к этому ответу за исключением явных ошибок, которые не зависят от архитектуры. Вдохновленный доблестными усилиями 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
Псевдоалгоритм двоичного поиска, чтобы получить не цифру 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;
Разделите на 10 в цикле, пока результат не достигнет нуля. Количество итераций будет соответствовать количеству десятичных цифр.
Предполагая, что вы ожидаете получить 0 цифр в нулевом значении:
int countDigits( int value )
{
int result = 0;
while( value != 0 ) {
value /= 10;
result++;
}
return result;
}
Вот очень быстрый метод вычисления количества десятичных цифр Кендалла Виллетса :
int count_digits(uint32_t n) {
#if defined(__has_builtin) && __has_builtin(__builtin_clz)
// This increments the upper 32 bits (log10(T) - 1) when >= T is added.
# define K(T) (((sizeof(#T) - 1ull) << 32) - T)
static const uint64_t table[] = {
K(0), K(0), K(0), // 8
K(10), K(10), K(10), // 64
K(100), K(100), K(100), // 512
K(1000), K(1000), K(1000), // 4096
K(10000), K(10000), K(10000), // 32k
K(100000), K(100000), K(100000), // 256k
K(1000000), K(1000000), K(1000000), // 2048k
K(10000000), K(10000000), K(10000000), // 16M
K(100000000), K(100000000), K(100000000), // 128M
K(1000000000), K(1000000000), K(1000000000), // 1024M
K(1000000000), K(1000000000) // 4B
};
return (n + table[__builtin_clz(n | 1) ^ 31]) >> 32u;
#else
int count = 1;
for (;;) {
if (n < 10) return count;
if (n < 100) return count + 1;
if (n < 1000) return count + 2;
if (n < 10000) return count + 3;
n /= 10000u;
count += 4;
}
return count;
#endif
}
Быстрый путь зависит от __builtin_clz который доступен в GCC и clang, но благодаря резервному варианту, который работает достаточно хорошо
count_digits полностью портативен.
Это генерирует очень эффективный код (Godbolt):
count_digits(unsigned int):
mov edx, edi
mov eax, edi
or edx, 1
bsr edx, edx
movsx rdx, edx
add rax, QWORD PTR count_digits(unsigned int)::table[0+rdx*8]
shr rax, 32
ret
Версия с постоянной стоимостью, использующая сборку x86 и справочную таблицу:
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 );
}
Еще один, с меньшей таблицей поиска и приближением log10, взятым отсюда.
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]));
}
Оба из них используют тот факт, что в x86 -INT_MIN равен INT_MIN.
Обновить:
Согласно предложению, здесь приведены временные параметры для count_bsr и немного более быстрых 64-битных подпрограмм count_bsr_mod only по сравнению с бинарным поиском и бинарными алгоритмами chop с использованием очень хорошей тестовой программы paxdiablo, модифицированной для генерации множеств со случайным распределением знаков. Тесты были построены с использованием gcc 4.9.2 с использованием опций "-O3 -falign-functions=16 -falign-jumps=16 -march=corei7-avx" и выполнялись в спокойной в противном случае системе Sandy Bridge с отключенными состояниями турбо и сна.
Время для бср мод: 270000 Время для BSR: 340000 Время для бинарной отбивной: 800000 Время для двоичного поиска: 770000 Время для бинарного поиска мод: 470000
Источник для теста,
#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 \n\t"
"xorl %%edx, %0 \n\t"
"subl %%edx, %0 \n\t"
"movl %0, %%edx \n\t"
"bsrl %0, %0 \n\t"
"shlq $32, %%rdx \n\t"
"movq %P1(,%q0,8), %q0 \n\t"
"cmpq %q0, %%rdx \n\t"
"setg %%dl \n\t"
"addl %%edx, %0 \n\t"
: "+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 %d\n", INT_MIN, count_bsearch(INT_MIN));
//for (i = -1000000000; i != 0; i /= 10)
for (i = -999999999; i != 0; i /= 10)
printf ("%11d %d\n", i, count_bsearch(i));
printf ("%11d %d\n", 0, count_bsearch(0));
for (i = 1; i != 1000000000; i *= 10)
printf ("%11d %d\n", i, count_bsearch(i));
printf ("%11d %d\n", 1000000000, count_bsearch(1000000000));
printf ("%11d %d\n", 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 %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;
}
Из Бит Тиддлинг Хаки:
Найти целочисленные логарифм базы 10 из целых чисел очевидным способом
Обратите внимание на порядок сравнений в нем.
Вот развернутый бинарный поиск без деления или умножения. В зависимости от распределения чисел, данных ему, он может или не может побить другие, сделанные с развернутыми операторами if, но всегда должен побеждать те, которые используют циклы и умножение / деление /log10.
С равномерным распределением случайных чисел, охватывающим весь диапазон, на моей машине это составляло в среднем 79% времени выполнения paxdiablo count_bchop(), 88% времени count_ifs() и 97% времени count_revifs().
С экспоненциальным распределением (вероятность того, что число, имеющее n цифр, равно вероятности того, что число имеет m цифр, где m ≠ n), count_ifs() и count_revifs () оба превзойдут мою функцию. Я не уверен, почему на этом этапе.
int count_bsearch(int i)
{
if (i < 0)
{
if (i == INT_MIN)
return 10; // 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;
}
}
}
Ты можешь сделать:floor (log10 (abs (x))) + 1Или, если вы хотите сэкономить на циклах, вы можете просто сделать сравнение
if(x<10)
return 1;
if(x<100)
return 2;
if(x<1000)
return 3;
etc etc
Это позволяет избежать любых дорогостоящих в вычислительном отношении функций, таких как логарифм или даже умножение или деление. Хотя это не элегантно, это можно скрыть, заключив его в функцию. Это не сложно или сложно поддерживать, поэтому я бы не отказался от этого подхода из-за плохой практики кодирования; Я чувствую, что это будет выбросить ребенка с водой в ванной.
Я наткнулся на это во время поиска в Google: http://www.hackersdelight.org/hdcodetxt/ilog.c.txt
Быстрый бенчмарк наглядно показал выигрыш бинарных методов поиска. Код Лакшманараджа довольно хорош, у Александра Коробки на 30% быстрее, у Deadcode чуть-чуть быстрее (~10%), но я обнаружил, что следующие трюки из приведенной выше ссылки дают дополнительное улучшение на 10%.
// Integer log base 10, modified binary search.
int ilog10c(unsigned x) {
if (x > 99)
if (x < 1000000)
if (x < 10000)
return 3 + ((int)(x - 1000) >> 31);
// return 3 - ((x - 1000) >> 31); // Alternative.
// return 2 + ((999 - x) >> 31); // Alternative.
// return 2 + ((x + 2147482648) >> 31); // Alternative.
else
return 5 + ((int)(x - 100000) >> 31);
else
if (x < 100000000)
return 7 + ((int)(x - 10000000) >> 31);
else
return 9 + ((int)((x-1000000000)&~x) >> 31);
// return 8 + (((x + 1147483648) | x) >> 31); // Alternative.
else
if (x > 9)
return 1;
else
return ((int)(x - 1) >> 31);
// return ((int)(x - 1) >> 31) | ((unsigned)(9 - x) >> 31); // Alt.
// return (x > 9) + (x > 0) - 1; // Alt.
}
Обратите внимание, что это журнал 10, а не количество цифр, поэтому digits = ilog10c(x)+1,
Не поддерживает негативы, но это легко исправить с помощью -,
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 - мое любимое решение.
Немного подстроимся под язык Си:
floor( log10( abs( (number)?number:1 ) ) + 1 );
Я знаю, что опаздываю, но этот код в + 10 раз быстрее всех других ответов.
int digits(long long x)
{
x < 0 ? x = -x : 0;
return x < 10 ? 1 :
x < 100 ? 2 :
x < 1000 ? 3 :
x < 10000 ? 4 :
x < 100000 ? 5 :
x < 1000000 ? 6 :
x < 10000000 ? 7 :
x < 100000000 ? 8 :
x < 1000000000 ? 9 :
x < 10000000000 ? 10 : 0;
}
...
int x = -937810;
printf("%d : %d digits\n", x, digits(x));
Из:
-937810 : 6 digits
Поскольку никто не упомянул, менее 10^ можно сделать с помощью SIMD. Вот реализация с библиотекой eve для sse2, avx2 и arm-v8.
https://godbolt.org/z/nabPsovqE
Не знаю, насколько это быстро, хотя AVX-2 выглядит неплохо
count_digits(int): # @count_digits(int)
vmovd xmm0, edi
vpbroadcastd ymm0, xmm0
vmovdqa ymm1, ymmword ptr [rip + .LCPI0_0] # ymm1 = [10,100,1000,10000,100000,1000000,10000000,100000000]
vpcmpgtd ymm0, ymm1, ymm0
vmovmskps ecx, ymm0
bsf edx, ecx
add edx, 1
xor esi, esi
cmp edi, 1000000000
setl sil
mov eax, 10
sub eax, esi
test cl, cl
cmovne eax, edx
vzeroupper
ret
Простой способ найти длину (то есть количество цифр) целого числа со знаком заключается в следующем:
while ( abs(n) > 9 )
{
num /= 10;
++len;
}
куда n целое число, которое вы хотите найти длину и где len равно количеству цифр в целом числе. Это работает для обоих значений n (отрицательный или положительный).
Вызов на abs() необязательно, если вы работаете только с положительными целыми числами.
НЕ используйте пол (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;
Где массив numbers[] содержит случайно сгенерированные числа во всем диапазоне типа 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. О_О. Теперь это впечатляет. Он был оптимизирован гораздо лучше, чем я думал, избегая большинства веток действительно умными способами. Не удивительно, что это БЫСТРО.
Я думаю, самый простой способ был бы:
int digits = 0;
if (number < 0) digits = 1;
while (number) {
number /= 10;
digits++;
}
цифры дают ответ.
void main()
{
int a,i;
printf("Enter the number :");
scanf("%d",&a);
while(a>0)
{
a=a/10;
i++;
}
getch();
}
Вы можете найти количество цифр в числе, используя этот формат ceil (log10 (abs (x))), где ceil возвращает целое число, которое больше, чем число
Для C# вот очень быстрое и простое решение...
private static int NumberOfPlaces(int n)
{
//fast way to get number of digits
//converts to signed string with +/- intact then accounts for it by subtracting 1
return n.ToString("+#;-#;+0").Length-1;
}