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

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 2

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 3

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 4

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 5

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 6

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

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 9

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 10

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

Answer 11

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 12

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 13

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 14

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