How do I determine the number of digits of an integer in C?
CMathC Problem Overview
for instance,
n = 3432, result 4
n = 45, result 2
n = 33215, result 5
n = -357, result 3
I guess I could just turn it into a string then get the length of the string but that seems convoluted and hack-y.
C Solutions
Solution 1 - C
The recursive approach :-)
int numPlaces (int n) {
if (n < 0) return numPlaces ((n == INT_MIN) ? INT_MAX: -n);
if (n < 10) return 1;
return 1 + numPlaces (n / 10);
}
Or iterative:
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;
}
Or raw speed:
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;
}
Those above have been modified to better process MININT. On any weird systems that don't follow sensible 2n two's complement rules for integers, they may need further adjustment.
The raw speed version actually outperforms the floating point version, modified below:
int numPlaces (int n) {
if (n == 0) return 1;
return floor (log10 (abs (n))) + 1;
}
With a hundred million iterations, I get the following results:
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
That actually surprised me a little - I thought the Intel chips had a decent FPU but I guess general FP operations still can't compete with hand-optimized integer code.
Update following stormsoul's suggestions:
Testing the multiply-iterative solution by stormsoul gives a result of 4 seconds so, while it's much faster than the divide-iterative solution, it still doesn't match the optimized if-statement solution.
Choosing the arguments from a pool of 1000 randomly generated numbers pushed the raw speed time out to 2 seconds so, while it appears there may have been some advantage to having the same argument each time, it's still the fastest approach listed.
Compiling with -O2 improved the speeds but not the relative positions (I increased the iteration count by a factor of ten to check this).
Any further analysis is going to have to get seriously into the inner workings of CPU efficiency (different types of optimization, use of caches, branch prediction, which CPU you actually have, the ambient temperature in the room and so on) which is going to get in the way of my paid work :-). It's been an interesting diversion but, at some point, the return on investment for optimization becomes too small to matter. I think we've got enough solutions to have answered the question (which was, after all, not about speed).
Further update:
This will be my final update to this answer barring glaring errors that aren't dependent on architecture. Inspired by stormsoul's valiant efforts to measure, I'm posting my test program (modified as per stormsoul's own test program) along with some sample figures for all methods shown in the answers here. Keep in mind this is on a particular machine, your mileage may vary depending on where you run it (which is why I'm posting the test code).
Do with it as you wish:
#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;
}
> Remember that you need to ensure you use the correct command line to compile it. In particular, you may need to explicitly list the math library to get log10() working. The command line I used under Debian was gcc -o testprog testprog.c -lm.
And, in terms of results, here's the leader-board for my environment:
Optimization level 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
Optimization level 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
Solution 2 - C
floor (log10 (abs (x))) + 1
Solution 3 - C
The shortest answer: snprintf(0,0,"%+d",n)-1
Solution 4 - C
Binary search pseudo algorithm to get no of digits of r in 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;
Solution 5 - C
Here is a very fast method to compute the number of decimal digits by Kendall Willets:
int count_digits(uint32_t n) {
#ifndef __has_builtin
# define __has_builtin(x) 0
#endif
#if __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
}
The fast path relies on __builtin_clz which is available in GCC and clang but thanks to the fallback that works reasonably well count_digits is fully portable.
This generates very efficient code (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
Solution 6 - C
Divide by 10 in a loop until the result reaches zero. The number of iterations will correspond to the number of decimal digits.
Assuming that you expect to get 0 digits in a zero value:
int countDigits( int value )
{
int result = 0;
while( value != 0 ) {
value /= 10;
result++;
}
return result;
}
Solution 7 - C
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 \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;
}
Solution 8 - C
You can do:
floor (log10 (abs (x))) + 1
Or if you want to save on cycles you could just do comparisons
if(x<10)
return 1;
if(x<100)
return 2;
if(x<1000)
return 3;
etc etc
This avoids any computationally expensive functions such as log or even multiplication or division. While it is inelegant this can be hidden by encapsulating it into a function. It isn't complex or difficult to maintain so I would not dismiss this approach on account of poor coding practice; I feel to do so would be throwing the baby out with the bath water.
Solution 9 - C
Here is an unrolled binary search without any division or multiplication. Depending on the distribution of numbers given to it, it may or may not beat the other ones done with unrolled if statements, but should always beat the ones that use loops and multiplication/division/log10.
With a uniform distribution of random numbers encompassing the whole range, on my machine it averaged 79% of the execution time of paxdiablo's count_bchop(), 88% the time of count_ifs(), and 97% of the time of count_revifs().
With an exponential distribution (the probability of a number having n digits is equal to the that of it having m digits, where m ≠ n) count_ifs() and count_revifs() both beat my function. I'm not sure why at this point.
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;
}
}
}
Solution 10 - C
From Bit Twiddling Hacks :
Find integer log base 10 of an integer the obvious way
Note the ordering of comparisons in it.
Solution 11 - C
I stumbled across this during a google search: http://web.archive.org/web/20190108211528/http://www.hackersdelight.org/hdcodetxt/ilog.c.txt
A quick benchmark clearly showed the binary search methods winning. lakshmanaraj's code is quite good, Alexander Korobka's is ~30% faster, Deadcode's is a tiny bit faster still (~10%), but I found the following tricks from the above link give a further 10% improvement.
// 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.
}
Note this is log 10, not number of digits, so digits = ilog10c(x)+1.
Doesn't support negatives, but that's easily fixed with a -.
Solution 12 - C
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
Very inelegant. But quicker than all the other solutions. Integer Division and FP logs are expensive to do. If performance isn't an issue, the log10 solution is my favorite.
Solution 13 - C
int n = 437788;
int N = 1;
while (n /= 10) N++;
Solution 14 - C
Just a little adjust for C language:
floor( log10( abs( (number)?number:1 ) ) + 1 );
Solution 15 - C
Since no-one mentioned, the less than 10^ can be done with SIMD. Here is an implementation with an eve library for sse2, avx2 and arm-v8.
https://godbolt.org/z/bscr3MWr4
I don't know how fast this is, though AVX-2 looks quite nice
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
Solution 16 - C
DON'T use floor(log10(...)). These are floating-point functions, and slow ones, to add. I believe the fastest way would be this function:
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;
}
}
Note that the binary search version some people suggested could be slower due to branch mispredictions.
EDIT:
I did some testing, and got some really interesting results. I timed my function together with all the functions tested by Pax, AND the binary search function given by lakshmanaraj. The testing is done by the following code snippet:
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;
Where the numbers[] array contains randomly generated numbers over the entire range of the int type (barring MIN_INT). The testing was repeated for each tested function on THE SAME numbers[] array. The entire test was made 10 times, with results averaged over all passes. The code was compiled with GCC 4.3.2 with -O3 optimization level.
Here are the results:
floating-point log10: 10340ms
recursive divide: 3391ms
iterative divide: 2289ms
iterative multiplication: 1071ms
unrolled tests: 859ms
binary search: 539ms
I must say I got really astonished. The binary search performed far better than I thought it would. I checked out how GCC compiled this code to asm. O_O. Now THIS is impressive. It got optimized much better than I thought possible, avoiding most branches in really clever ways. No wonder it is FAST.
Solution 17 - C
you can find number of digits in a number by using this formaula ceil (log10 (abs (x))) where ceil returns a integer number just greater than number
Solution 18 - C
I guess, the simplest way would be:
int digits = 0;
if (number < 0) digits = 1;
while (number) {
number /= 10;
digits++;
}
digits gives the answer.
Solution 19 - C
A simple way to find the length (i.e number of digits) of signed integer is this:
while ( abs(n) > 9 )
{
num /= 10;
++len;
}
Where n is the integer you want to find the length of and where len is equal to the number of digits in the integer. This works for both values of n (negative or positive).
The call on abs() is optional, if you are only working with positive integers.
Solution 20 - C
void main()
{
int a,i;
printf("Enter the number :");
scanf("%d",&a);
while(a>0)
{
a=a/10;
i++;
}
getch();
}