Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Efficient way to determine number of digits in an integer

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.

#include <climits>

// 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 64-bit numbers
template <>
int numDigits(int64_t x) {
    if (x == INT64_MIN) return 19 + 1;
    if (x < 0) return digits(-x) + 1;

    if (x >= 10000000000) {
        if (x >= 100000000000000) {
            if (x >= 10000000000000000) {
                if (x >= 100000000000000000) {
                    if (x >= 1000000000000000000)
                        return 19;
                    return 18;
                }
                return 17;
            }
            if (x >= 1000000000000000)
                return 16;
            return 15;
        } 
        if (x >= 1000000000000) {
            if (x >= 10000000000000)
                return 14;
            return 13;
        }
        if (x >= 100000000000)
            return 12;
        return 11;
    }
    if (x >= 100000) {
        if (x >= 10000000) {
            if (x >= 100000000) {
                if (x >= 1000000000)
                    return 10;
                return 9;
            }
            return 8;
        }
        if (x >= 1000000)
            return 7;
        return 6;
    }
    if (x >= 100) {
        if (x >= 1000) {
            if (x >= 10000)
                return 5;
            return 4;
        }
        return 3;
    }
    if (x >= 10)
        return 2;
    return 1;
}

// partial specialization optimization for 32-bit numbers
template<>
int numDigits(int32_t x)
{
    if (x == INT32_MIN) 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];
}

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.


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

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


Practical joke: This is the most efficient way (number of digits is calculated at compile-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.


convert to string and then use built-in functions

unsigned int i;
cout<< to_string(i).length()<<endl;

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.