Tutorial :What's the best way to get the length of the decimal representation of an int in C++?



Question:

What's the best way to write

int NumDigits(int n);  

in C++ which would return the number of digits in the decimal representation of the input. For example 11->2, 999->3, -1->2 etc etc.


Solution:1

Clean and fast, and independent of sizeof(int):

int NumDigits(int n) {      int digits = 0;      if (n <= 0) {          n = -n;          ++digits;      }      while (n) {          n /= 10;          ++digits;      }      return digits;  }  


Solution:2

//Works for positive integers only  int DecimalLength(int n) {      return floor(log10f(n) + 1);  }  


Solution:3

The fastest way is probably a binary search...

//assuming n is positive  if (n < 10000)      if (n < 100)          if (n < 10)              return 1;          else              return 2;      else          if (n < 1000)              return 3;          else              return 4;   else       //etc up to 1000000000  

In this case it's about 3 comparisons regardless of input, which I suspect is much faster than a division loop or using doubles.


Solution:4

One way is to (may not be most efficient) convert it to a string and find the length of the string. Like:

int getDigits(int n)  {      std::ostringstream stream;      stream<<n;        return stream.str().length();  }  


Solution:5

To extend Arteluis' answer, you could use templates to generate the comparisons:

template<int BASE, int EXP>  struct Power  {      enum {RESULT = BASE * Power<BASE, EXP - 1>::RESULT};  };    template<int BASE>  struct Power<BASE, 0>  {      enum {RESULT = 1};  };    template<int LOW = 0, int HIGH = 8>  struct NumDigits  {      enum {MID = (LOW + HIGH + 1) / 2};        inline static int calculate (int i)      {          if (i < Power<10, MID>::RESULT)              return NumDigits<LOW, MID - 1>::calculate (i);          else              return NumDigits<MID, HIGH>::calculate (i);      }  };    template<int LOW>  struct NumDigits<LOW, LOW>  {      inline static int calculate (int i)      {          return LOW + 1;      }  };    int main (int argc, char* argv[])  {      // Example call.      std::cout << NumDigits<>::calculate (1234567) << std::endl;        return 0;  }  


Solution:6

numdigits = snprintf(NULL, 0, "%d", num);  


Solution:7

int NumDigits(int n)  {    int digits = 0;      if (n < 0) {      ++digits;      do {        ++digits;        n /= 10;      } while (n < 0);    }    else {      do {        ++digits;        n /= 10;      } while (n > 0);    }      return digits;  }  

Edit: Corrected edge case behavior for -2^31 (etc.)


Solution:8

Some very over-complicated solutions have been proposed, including the accepted one.

Consider:

#include <cmath>  #include <cstdlib>    int NumDigits( int num )  {      int digits = (int)log10( (double)abs(num) ) + 1 ;        return num >= 0 ? digits : digits + 1 ;  }  

Note that it works for for INT_MIN + 1 ... INT_MAX, because abs(INT_MIN) == INT_MAX + 1 == INT_MIN (due to wrap-around), which in-turn is invalid input to log10(). It is possible to add code for that one case.


Solution:9

Another implementation using STL binary search on a lookup table, which seems not bad (not too long and still faster than division methods). It also seem easy and efficient to adapt for type much bigger than int: will be faster than O(digits) methods and just needs multiplication (no division or log function for this hypothetical type). There is a requirement of a MAXVALUE, though. Unless you fill the table dynamically.

[edit: move the struct into the function]

int NumDigits9(int n) {      struct power10{          vector<int> data;          power10() {               for(int i=10; i < MAX_INT/10; i *= 10) data.push_back(i);          }      };        static const power10 p10;      return 1 + upper_bound(p10.data.begin(), p10.data.end(), n) - p10.data.begin();  }  


Solution:10

My version of loop (works with 0, negative and positive values):

int numDigits(int n)  {     int digits = n<0;  //count "minus"     do { digits++; } while (n/=10);     return digits;  }  


Solution:11

If you're using a version of C++ which include C99 maths functions (C++0x and some earlier compilers)

static const double log10_2 = 3.32192809;    int count_digits ( int n )  {      if ( n == 0 ) return 1;      if ( n < 0 ) return ilogb ( -(double)n ) / log10_2 + 2;      return ilogb ( n ) / log10_2 + 1;  }  

Whether ilogb is faster than a loop will depend on the architecture, but it's useful enough for this kind of problem to have been added to the standard.


Solution:12

An optimization of the previous division methods. (BTW they all test if n!=0, but most of the time n>=10 seems enough and spare one division which was more expensive).

I simply use multiplication and it seems to make it much faster (almost 4x here), at least on the 1..100000000 range. I am a bit surprised by such difference, so maybe this triggered some special compiler optimization or I missed something.

The initial change was simple, but unfortunately I needed to take care of a new overflow problem. It makes it less nice, but on my test case, the 10^6 trick more than compensates the cost of the added check. Obviously it depends on input distribution and you can also tweak this 10^6 value.

PS: Of course, this kind of optimization is just for fun :)

int NumDigits(int n) {      int digits = 1;      // reduce n to avoid overflow at the s*=10 step.      // n/=10 was enough but we reuse this to optimize big numbers      if (n >= 1000000) {          n /= 1000000;          digits += 6; // because 1000000 = 10^6      }      int s = 10;      while (s <= n) {          s *= 10;          ++digits;      }      return digits;  }  


Solution:13

Here's a simpler version of Alink's answer .

int NumDigits(int n)  {      if (n < 0)          return NumDigits(-n) + 1;        static int MaxTable[9] = { 10,100,1000,10000,100000,1000000,10000000,100000000,1000000000 };      return 1 + (std::upper_bound(MaxTable, MaxTable+9, n) - MaxTable);  }  

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »