How to determine the number of digits of an integer in C?

Question

eg,

n = 3432, result 4 n = 45, result 2 n = 33215, result 5 n = -357, result 3 

I think I could just turn it into a string and then get the length of the string, but that seems confusing and hacked.

Answer 1

 floor (log10 (abs (x))) + 1 

http://en.wikipedia.org/wiki/Logarithm

Answer 2

Recursive approach :-)

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

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

The ones above have been modified to improve the MININT process. In any strange systems that do not follow the reasonable 2 ⁿ two complement rules for integers, they may need additional adjustment.

The raw version of speed actually surpasses 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 

This actually surprised me a little - I thought that Intel chips have a decent FPU, but I believe that general FP operations still cannot compete with the whole code optimized manually.

Update the following stormsoul sentences:

Testing a multiple-iterative solution by stormsoul gives a result of 4 seconds, therefore, although it is much faster than a solution with delimited iterations, it still does not match the optimized if-statement solution.

Choosing arguments from a pool of 1000 randomly generated numbers pushed the raw speed time up to 2 seconds, so although it does appear there may have been some advantage to having the same argument every time, but it is still the fastest approach.

Compiling with -O2 improved speed, but not relative positions (I increased the number of iterations tenfold to verify this).

Any further analysis should seriously deal with the internal workings of CPU efficiency (various types of optimization, using caches, predicting branches, which processor you actually have, the ambient temperature in the room, etc.), which will interfere with my paid work: - ) It was interesting entertainment, but at some point, the return on investment for optimization becomes too small to make a difference. I think we have enough solutions to answer the question (which was, after all, not about speed).

Further update:

This will be my last update to this answer, prohibiting flagrant errors that are architecture independent. Inspired by rapid measuring standards, I submit my test program (modified according to my own test program), as well as some examples for all the methods shown in the answers here. Keep in mind that this is on a specific machine, your mileage may vary depending on where you run it (which is why I am sending a test code).

Do as you want with this:

 #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 make sure that you are using the correct command line to compile it. In particular, you may need to explicitly specify the math library for log10() to work. The command line I used on Debian was gcc -o testprog testprog.c -lm .

And, in terms of results, here is the leaderboard 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 

Answer 3

The binary search pseudo-algorithm does not receive digits from r to 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; 

Answer 4

The shortest answer: snprintf(0,0,"%+d",n)-1

Answer 5

Divide by 10 in a loop until the result reaches zero. The number of iterations will correspond to the number of decimal digits.

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

Answer 6

You can do: floor (log10 (abs (x))) + 1 Or, if you want to save on loops, 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 costly computing functions, such as a log or even multiplication or division. Although it is not elegant, it can be hidden by encapsulating it in a function. It is not difficult or difficult to maintain, so I would not abandon this approach due to poor coding practice; I feel this will make the baby throw bath water.

Answer 7

Fixed cost version using x86 build and 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 them use the fact that on x86 -INT_MIN is INT_MIN.

Update:

As suggested, here are the timings for count_bsr and some faster 64-bit count_bsr_mod routines compared to binary search and binary algorithms using the very nice paxdiablo testing program, modified to generate sets with random sign distribution. Tests were built using gcc 4.9.2 using the options "-O3 -falign-functions = 16 -falign-jumps = 16 -march = corei7-avx" and were run in a quiet Sandy Bridge system with turbo and sleep modes turned 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 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; } 

Answer 8

From bit-wandering hacks:

Find the integer database 10 of an integer in an obvious way

Pay attention to the comparison order in it.

Answer 9

Here is a detailed binary search without any division or multiplication. Depending on the distribution of the numbers assigned to it, it may or may not beat others executed using the expanded if statements, but it must always beat those that use cycles and multiplication / division / log10.

With the even distribution of random numbers spanning the entire range, on my machine it averaged 79% of the paxdiablo count_bchop () runtime, 88% of the count_ifs () time, and 97% of the count_revifs () time.

With an exponential distribution (the probability of a number containing n digits is equal to that of it, which has 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 11; // special case for -2^31 because 2^31 can't fit in a two 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; } } } 

Answer 10

I stumbled upon this while searching on google: http://www.hackersdelight.org/hdcodetxt/ilog.c.txt

A quick test showed that binary search methods win. the lakshmanaraj code is pretty good, Alexander Box is 30% faster, Deadcode's is a little faster (~ 10%), but I found that the following tricks from the above link give another 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 that this is a log of 10, not the number of digits, so digits = ilog10c(x)+1 .

It does not support negatives, but it is easily fixed with - .

Answer 11

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

Answer 12

 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 faster than all other solutions. Target unit and FP logs are expensive. If performance is not an issue, log10 solution is my favorite.

Answer 13

Tweak the C language a bit:

 floor( log10( abs( (number)?number:1 ) ) + 1 ); 

Answer 14

DO NOT use gender (log10 (...)). These are floating point functions and slow to add. I believe that 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; } } 

Please note that the binary search version suggested by some people may be slower due to incorrect industry predictions.

EDIT:

I did some testing and got some really interesting results. I assigned my function along with all the functions tested by Pax and the binary search function given by lakshmanaraj. Testing is performed using 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 in the entire range of type int (MIN_INT ban). Testing was repeated for each function being tested in the SAME numbers [] array. The entire test was carried out 10 times, the results were averaged over all passes. The code was compiled with GCC 4.3.2 with an optimization level of -O3.

Here are the results:

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

I have to say that I was very surprised. The binary search performed much better than I thought. I checked how GCC compiled this code in asm. O_O. Now it is impressive. It has been optimized much better than I thought, possibly avoiding most industries in a truly smart way. No wonder this is FAST.

Answer 15

you can find the number of digits in a number using this formula ceil (log10 (abs (x))), where ceil returns an integer greater than a number

Answer 16

I think the easiest way:

  int digits = 0; if (number < 0) digits = 1; while (number) { number /= 10; digits++; } 

numbers gives an answer.

Answer 17

A simple way to find the length (e.g. number of digits) of a signed integer:

 while ( abs(n) > 9 ) { num /= 10; ++len; } 

Where n is the integer in which you want to find the length and where len is equal to the number of digits in integers. This works for both n values ​​(negative or positive).

The abs() call is optional if you only work with positive integers.

Answer 18

 void main() { int a,i; printf("Enter the number :"); scanf("%d",&a); while(a>0) { a=a/10; i++; } getch(); }