[c++] Efficient way to determine number of digits in an integer


11 Answers

The simplest way is to do:

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

Question

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




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.




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.




Yet another code snippet, doing basically the same as Vitali's but employs binary search. Powers array is lazy initialized once per unsigned type instance. Signed type overload takes care of minus sign.

#include <limits>
#include <type_traits>
#include <array>

template <class T> 
size_t NumberOfDecPositions ( T v, typename std::enable_if<std::is_unsigned<T>::value>::type* = 0 )
{
    typedef std::array<T,std::numeric_limits<T>::digits10+1> array_type;
    static array_type powers_of_10;
    if ( powers_of_10.front() == 0 )
    {
        T n = 1;
        for ( T& i: powers_of_10 )
        {
            i = n;
            n *= 10;
        }
    }

    size_t l = 0, r = powers_of_10.size(), p;
    while ( l+1 < r )
    {
        p = (l+r)/2;
        if ( powers_of_10[p] <= v )
            l = p;
        else
            r = p;
    }
    return l + 1;
};

template <class T> 
size_t NumberOfDecPositions ( T v, typename std::enable_if<std::is_signed<T>::value>::type* = 0 )
{
    typedef typename std::make_unsigned<T>::type unsigned_type;
    if ( v < 0 )
        return NumberOfDecPositions ( static_cast<unsigned_type>(-v) ) + 1;
    else
        return NumberOfDecPositions ( static_cast<unsigned_type>(v) );
}

If anybody cares of further optimization, please note that the first element of powers array is never used, and the l appears with +1 2 times.




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.




for integer 'X' you want to know the number of digits , alright without using any loop , this solution act in one formula in one line only so this is the most optimal solution i have ever seen to this problem .

 int x = 1000 ; 
 cout<<numberOfDigits = 1+floor(log10(x))<<endl ; 



C++11 update of preferred solution:

#include <limits>
#include <type_traits>
        template <typename T>
        typename std::enable_if<std::numeric_limits<T>::is_integer, unsigned int>::type
        numberDigits(T value) {
            unsigned int digits = 0;
            if (value < 0) digits = 1;
            while (value) {
                value /= 10;
                ++digits;
            }
            return digits;
        }

prevents template instantiation with double, et. al.




 #include <iostream>
 #include <math.h>

 using namespace std;

 int main()
 {
     double num;
     int result;
     cout<<"Enter a number to find the number of digits,  not including decimal places: ";
     cin>>num;
     result = ((num<=1)? 1 : log10(num)+1);
     cout<<"Number of digits "<<result<<endl;
     return 0;
 }

This is probably the simplest way of solving your problem, assuming you only care about digits before the decimal and assuming anything less than 10 is just 1 digit.




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




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

Note: "0" will have 0 digits! If you need 0 to appear to have 1 digit, use:

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

(Thanks Kevin Fegan)

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




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



// Meta-program to calculate number of digits in (unsigned) 'N'.    
template <unsigned long long N, unsigned base=10>
struct numberlength
{   // http://.com/questions/1489830/
    enum { value = ( 1<=N && N<base ? 1 : 1+numberlength<N/base, base>::value ) };
};

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

{
    assert( (1 == numberlength<0,10>::value) );
}
assert( (1 == numberlength<1,10>::value) );
assert( (1 == numberlength<5,10>::value) );
assert( (1 == numberlength<9,10>::value) );

assert( (4 == numberlength<1000,10>::value) );
assert( (4 == numberlength<5000,10>::value) );
assert( (4 == numberlength<9999,10>::value) );





Related