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.

Answer 1

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

Answer 2

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

Answer 3

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.)

Answer 4

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.

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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.

Answer 10

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.

Answer 11

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

Answer 12

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

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