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

Straightforward and simple, 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 2

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

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

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

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

Answer 6

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

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

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

Answer 9

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

int NumDigits(int32_t n)
{
    if (n < 0) {
        if (n == std::numeric_limits<int32_t>::min())
            return 11;
        return NumDigits(-n) + 1;
    }

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

Answer 10

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 11

Since the goal is to be fast, this is a improvement on andrei alexandrescu's improvement. His version was already faster than the naive way (dividing by 10 at every digit). The version below is faster at least on x86-64 and ARM for most sizes.

Benchmarks for this version vs alexandrescu's version on my PR on facebook folly.

inline uint32_t digits10(uint64_t v)
{
  std::uint32_t result = 0;
  for (;;)
  {
    result += 1
            + (std::uint32_t)(v>=10)
            + (std::uint32_t)(v>=100)
            + (std::uint32_t)(v>=1000)
            + (std::uint32_t)(v>=10000)
            + (std::uint32_t)(v>=100000);
    if (v < 1000000) return result;
    v /= 1000000U;
  }
}

Answer 12

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 13

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 14

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