Efficient way to determine number of digits in an integer

Question

What is a very efficient way of determining how many digits there are in an integer in C++?

Answer 1

int digits = 0; while (number != 0) { number /= 10; digits++; }

Note: "0" will have 0 digits! Just do if (number == 0) { digits = 1; } if you need 0 to appear to have 1 digit.

In the end, use a profiler to know which of all the answers here will be faster on your machine...

Answer 2

previous works for number >= 1. Original poster probably wants to handle zero. Whether or not negative numbers should include the '-' printed out in usual representation.

It's also possible the original poster wants, effectively the magnitude of the largest representable integer in an implementation, which may be different.

Answer 3

Well, the most efficient way, presuming you know the size of the integer, would be a lookup. Should be faster than the much shorter logarithm based approach. If you don't care about counting the '-', remove the + 1.

// generic solution
template <class T>
int numDigits(T number)
{
    int digits = 0;
    if (number < 0) digits = 1; // remove this line if '-' counts as a digit
    while (number) {
        number /= 10;
        digits++;
    }
    return digits;
}

// partial specialization optimization for 32-bit numbers
template<>
int numDigits(int32_t x)
{
    if (x == MIN_INT) return 10 + 1;
    if (x < 0) return numDigits(-x) + 1;

    if (x >= 10000) {
        if (x >= 10000000) {
            if (x >= 100000000) {
                if (x >= 1000000000)
                    return 10;
                return 9;
            }
            return 8;
        }
        if (x >= 100000) {
            if (x >= 1000000)
                return 7;
            return 6;
        }
        return 5;
    }
    if (x >= 100) {
        if (x >= 1000)
            return 4;
        return 3;
    }
    if (x >= 10)
        return 2;
    return 1;
}

// partial-specialization optimization for 8-bit numbers
template <>
int numDigits(char n)
{
    // if you have the time, replace this with a static initialization to avoid
    // the initial overhead & unnecessary branch
    static char x[256] = {0};
    if (x[0] == 0) {
        for (char c = 1; c != 0; c++)
            x[c] = numDigits((int32_t)c);
        x[0] = 1;
    }
    return x[n];
}

Answer 4

The simplest way is to do:

void GetNumberOfDigits (unsigned i)
{
    return i > 0 ? (int) log10 ((double) i) + 1 : 1;
}

log10 is defined in <cmath> or <math.h>. You'd need to profile this to see if it's faster than any of the others posted here. I'm not sure how robust this is with regards to float point precision. Also, the argument is unsigned as negative values and log don't really mix.

Skizz

Answer 5

A previous poster suggested a loop that divides by 10. Since multiplies on modern machines are a lot faster, I'd recommend the following code instead:

 int digits = 1, pten=10; while ( pten <= number ) { digits++; pten*=10; }

Answer 6

Practical joke: This is the most efficient way (number of digits is calculated in compilte time):

template <unsigned long long N, size_t base=10>
struct numberlength
{
 enum { value = 1 + numberlength<N/base, base>::value };
};

template <size_t base>
struct numberlength<0, base>
{
 enum { value = 0 };
};

May be useful to determine the width required for number field in formatting, input elements etc.

Answer 7

Here's a different approach:

digits = sprintf(numArr, "%d", num);    // where numArr is a char array
if (num < 0)
    digits--;

This may not be efficient, just something different than what others suggested.

Answer 8

See Bit Twiddling Hacks for a much shorter version of the answer you accepted. It also has the benefit of finding the answer sooner if your input is normally distributed, by checking the big constants first. (v >= 1000000000) catches 76% of the values, so checking that first will on average be faster.

Answer 9

I like Ira Baxter's answer. Here is a template variant that handles the various sizes and deals with the maximum integer values (updated to hoist the upper bound check out of the loop):

#include <boost/integer_traits.hpp>

template<typename T> T max_decimal()
{
    T t = 1;

    for (unsigned i = boost::integer_traits<T>::digits10; i; --i)
        t *= 10;

    return t;
}

template<typename T>
unsigned digits(T v)
{
    if (v < 0) v = -v;

    if (max_decimal<T>() <= v)
        return boost::integer_traits<T>::digits10 + 1;

    unsigned digits = 1;
    T boundary = 10;

    while (boundary <= v) {
        boundary *= 10;
        ++digits;
    }

    return digits;
}

To actually get the improved performance from hoisting the additional test out of the loop, you need to specialise max_decimal() to return constants for each type on your platform. A sufficiently magic compiler could optimise the call to max_decimal() to a constant, but specialisation is better with most compilers today. As it stands, this version is probably slower because max_decimal costs more than the tests removed from the loop.

I'll leave all that as an exercise for the reader.

Answer 10

template <typename type>
class number_of_decimal_digits {   
    const powers_and_max<type> mPowersAndMax;
public:
    number_of_decimal_digits(){
    }   
    inline size_t ndigits( type i) const {
        if(i<0){
             i += (i == std::numeric_limits<type>::min());
             i=-i;
        }
        const type* begin = &*mPowersAndMax.begin();
        const type* end = begin+mPowersAndMax.size();
        return 1 + std::lower_bound(begin,end,i) - begin;
    }
    inline size_t string_ndigits(const type& i) const {
        return (i<0) + ndigits(i);
    }
    inline size_t operator[](const type& i) const {
       return string_ndigits(i);
    }
};

where in powers_and_max we have (10^n)-1 for all n such that

(10^n) < std::numeric_limits<type>::max()

and std::numeric_limits<type>::max() in an array:

template <typename type>
struct powers_and_max : protected std::vector<type>{
    typedef std::vector<type> super;
    using super::const_iterator;
    using super::size;
    type& operator[](size_t i)const{return super::operator[](i)};
    const_iterator begin()const {return super::begin();} 
    const_iterator end()const {return super::end();} 
    powers_and_max() {
       const int size = (int)(log10(double(std::numeric_limits<type>::max())));
       int j = 0;
       type i = 10;
       for( ; j<size ;++j){
           push_back(i-1);//9,99,999,9999 etc;
           i*=10;
       }
       ASSERT(back()<std::numeric_limits<type>::max());
       push_back(std::numeric_limits<type>::max());
   }
};

here's a simple test:

number_of_decimal_digits<int>  ndd;
ASSERT(ndd[0]==1);
ASSERT(ndd[9]==1);
ASSERT(ndd[10]==2);
ASSERT(ndd[-10]==3);
ASSERT(ndd[-1]==2);
ASSERT(ndd[-9]==2);
ASSERT(ndd[1000000000]==10);
ASSERT(ndd[0x7fffffff]==10);
ASSERT(ndd[-1000000000]==11);
ASSERT(ndd[0x80000000]==11);

Of course any other implementation of an ordered set might be used for powers_and_max and if there was knowledge that there would be clustering but no knowledge of where the cluster might be perhaps a self adjusting tree implementation might be best

Answer 11

The ppc architecture has a bit counting instruction. With that, you can determine the log base 2 of a positive integer in a single instruction. For example, 32 bit would be:

#define log_2_32_ppc(x) (31-__cntlzw(x))

If you can handle a small margin of error on large values you can convert that to log base 10 with another few instructions:

#define log_10_estimate_32_ppc(x) (9-(((__cntlzw(x)*1233)+1545)>>12))

This is platform specific and slightly inaccurate, but also involves no branches, division or conversion to floating point. All depends on what you need.

I only know the ppc instructions off hand, but other architectures should have similar instructions.

Answer 12

effective way

int num;
int count = 0;
while(num)
{
   num /= 10;
   ++count;
}

---

#include <iostream>

int main()
{
   int num;
   std::cin >> num;

   std::cout << "number of digits for " << num << ": ";

   int count = 0;
   while(num)
   {
      num /= 10;
      ++count;
   }

   std::cout << count << '\n';

   return 0;
}

Answer 13

Perhaps I misunderstood the question but doesn't this do it?

int NumDigits(int x)  
{  
    x = abs(x);  
    return (x < 10 ? 1 :   
     (x < 100 ? 2 :   
     (x < 1000 ? 3 :   
     (x < 10000 ? 4 :   
     (x < 100000 ? 5 :   
     (x < 1000000 ? 6 :   
     (x < 10000000 ? 7 :  
     (x < 100000000 ? 8 :  
     (x < 1000000000 ? 9 :  
     10)))))))));  
}