Effiziente Methode zur Bestimmung der Anzahl von Ziffern in einer Ganzzahl

Was ist eine sehr effiziente Methode, um zu bestimmen, wie viele Ziffern eine Ganzzahl in C ++ enthält?

Nun, der effizienteste Weg, vorausgesetzt Sie kennen die Größe der Ganzzahl, wäre eine Suche. Sollte schneller sein als der viel kürzere logarithmusbasierte Ansatz. Wenn Sie das '-' nicht zählen möchten, entfernen Sie die + 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];
}

Der einfachste Weg ist:

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

log10 ist in <cmath>oder definiert <math.h>. Sie müssen dies profilieren, um zu sehen, ob es schneller ist als alle anderen hier veröffentlichten. Ich bin mir nicht sicher, wie robust dies in Bezug auf die Gleitkommapräzision ist. Außerdem ist das Argument nicht vorzeichenbehaftet, da negative Werte und Protokoll nicht wirklich gemischt werden.

Vielleicht habe ich die Frage falsch verstanden, aber tut das nicht?

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

Hinweis: "0" hat 0 Ziffern! Wenn Sie 0 benötigen, um eine Ziffer zu haben, verwenden Sie:

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

(Danke Kevin Fegan)

Verwenden Sie am Ende einen Profiler, um zu wissen, welche der hier aufgeführten Antworten auf Ihrem Computer schneller ist ...

Praktischer Witz: Dies ist der effizienteste Weg (die Anzahl der Ziffern wird zur Kompilierungszeit berechnet):

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

Kann nützlich sein, um die Breite zu bestimmen, die für das Zahlenfeld bei Formatierungen, Eingabeelementen usw. erforderlich ist.

Unter Bit Twiddling Hacks finden Sie eine viel kürzere Version der Antwort, die Sie akzeptiert haben. Es hat auch den Vorteil, dass Sie die Antwort früher finden, wenn Ihre Eingabe normal verteilt ist, indem Sie zuerst die großen Konstanten überprüfen. (v >= 1000000000)fängt 76% der Werte ab, sodass die Überprüfung im Durchschnitt schneller ist.

In String konvertieren und dann integrierte Funktionen verwenden

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

int x = 1000;
int numberOfDigits = x ? static_cast<int>(log10(abs(x))) + 1 : 1;

Ein vorheriges Poster schlug eine Schleife vor, die durch 10 geteilt wird. Da Multiplikationen auf modernen Maschinen viel schneller sind, würde ich stattdessen den folgenden Code empfehlen:

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

Die ppc-Architektur hat eine Bitzählanweisung. Damit können Sie die Protokollbasis 2 einer positiven Ganzzahl in einem einzigen Befehl bestimmen. Zum Beispiel wäre 32 Bit:

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

Wenn Sie mit einer kleinen Fehlerquote bei großen Werten umgehen können, können Sie diese mit ein paar weiteren Anweisungen in die Protokollbasis 10 konvertieren:

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

Dies ist plattformspezifisch und leicht ungenau, beinhaltet jedoch auch keine Verzweigungen, Unterteilungen oder Konvertierungen in Gleitkommazahlen. Alles hängt davon ab, was Sie brauchen.

Ich kenne die ppc-Anweisungen nur aus der Hand, aber andere Architekturen sollten ähnliche Anweisungen haben.

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

Dies ist wahrscheinlich der einfachste Weg, um Ihr Problem zu lösen, vorausgesetzt, Sie kümmern sich nur um Ziffern vor der Dezimalstelle und weniger als 10 ist nur eine Ziffer.

Ich mag Ira Baxters Antwort. Hier ist eine Vorlagenvariante, die die verschiedenen Größen behandelt und sich mit den maximalen Ganzzahlwerten befasst (aktualisiert, um den Check für die Obergrenze aus der Schleife zu heben):

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

Um die verbesserte Leistung zu erzielen, indem der zusätzliche Test aus der Schleife gehoben wird, müssen Sie max_decimal () spezialisieren, um Konstanten für jeden Typ auf Ihrer Plattform zurückzugeben. Ein ausreichend magischer Compiler könnte den Aufruf von max_decimal () auf eine Konstante optimieren, aber die Spezialisierung ist heute bei den meisten Compilern besser. Derzeit ist diese Version wahrscheinlich langsamer, da max_decimal mehr kostet als die aus der Schleife entfernten Tests.

Ich werde das alles als Übung für den Leser hinterlassen.

#include <stdint.h> // uint32_t [available since C99]

/// Determine the number of digits for a 32 bit integer.
/// - Uses at most 4 comparisons.
/// - (cX) 2014 [email protected]
/// - \see http://stackoverflow.com/questions/1489830/#27669966
/**  #d == Number length vs Number of comparisons == #c
     \code
         #d | #c   #d | #c
         ---+---   ---+---
         10 | 4     5 | 4
          9 | 4     4 | 4
          8 | 3     3 | 3
          7 | 3     2 | 3
          6 | 3     1 | 3
     \endcode
*/
unsigned NumDigits32bs(uint32_t x) {
    return // Num-># Digits->[0-9] 32->bits bs->Binary Search
    ( x >= 100000u // [6-10] [1-5]
    ?   // [6-10]
        ( x >= 10000000u // [8-10] [6-7]
        ?   // [8-10]
            ( x >= 100000000u // [9-10] [8]
            ? // [9-10]
                ( x >=  1000000000u // [10] [9]
                ?   10
                :    9
                )
            : 8
            )
        :   // [6-7]
            ( x >=  1000000u // [7] [6]
            ?   7
            :   6
            )
        )
    :   // [1-5]
        ( x >= 100u // [3-5] [1-2]
        ?   // [3-5]
            ( x >= 1000u // [4-5] [3]
            ? // [4-5]
                ( x >=  10000u // [5] [4]
                ?   5
                :   4
                )
            : 3
            )
        :   // [1-2]
            ( x >=  10u // [2] [1]
            ?   2
            :   1
            )
        )
    );
}

Noch ein Code-Snippet, das im Grunde das Gleiche wie Vitali macht, aber die binäre Suche verwendet. Das Powers-Array wird nur einmal pro Instanz vom Typ ohne Vorzeichen verzögert initialisiert. Die signierte Überladung sorgt für das Minuszeichen.

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

Wenn sich jemand für eine weitere Optimierung interessiert, beachten Sie bitte, dass das erste Element des Potenzarrays niemals verwendet wird und das zweimal langezeigt +1wird.

Falls die Anzahl der Ziffern UND der Wert jeder Ziffernposition benötigt wird, verwenden Sie Folgendes:

int64_t = number, digitValue, digits = 0;    // or "int" for 32bit

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

digitgibt Ihnen den Wert an der Nummernposition an, die derzeit in der Schleife verarbeitet wird. Für die Nummer 1776 lautet der Ziffernwert beispielsweise:
6 in der 1. Schleife
7 in der 2. Schleife
7 in der 3. Schleife
1 in der 4. Schleife

// Meta-program to calculate number of digits in (unsigned) 'N'.    
template <unsigned long long N, unsigned base=10>
struct numberlength
{   // http://stackoverflow.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) );

/// Determine the number of digits for a 64 bit integer.
/// - Uses at most 5 comparisons.
/// - (cX) 2014 [email protected]
/// - \see http://stackoverflow.com/questions/1489830/#27670035
/**  #d == Number length vs Number of comparisons == #c
     \code
         #d | #c   #d | #c     #d | #c   #d | #c
         ---+---   ---+---     ---+---   ---+---
         20 | 5    15 | 5      10 | 5     5 | 5
         19 | 5    14 | 5       9 | 5     4 | 5
         18 | 4    13 | 4       8 | 4     3 | 4
         17 | 4    12 | 4       7 | 4     2 | 4
         16 | 4    11 | 4       6 | 4     1 | 4
     \endcode
*/
unsigned NumDigits64bs(uint64_t x) {
    return // Num-># Digits->[0-9] 64->bits bs->Binary Search
    ( x >= 10000000000ul // [11-20] [1-10]
    ?
        ( x >= 1000000000000000ul // [16-20] [11-15]
        ?   // [16-20]
            ( x >= 100000000000000000ul // [18-20] [16-17]
            ?   // [18-20]
                ( x >= 1000000000000000000ul // [19-20] [18]
                ? // [19-20]
                    ( x >=  10000000000000000000ul // [20] [19]
                    ?   20
                    :   19
                    )
                : 18
                )
            :   // [16-17]
                ( x >=  10000000000000000ul // [17] [16]
                ?   17
                :   16
                )
            )
        :   // [11-15]
            ( x >= 1000000000000ul // [13-15] [11-12]
            ?   // [13-15]
                ( x >= 10000000000000ul // [14-15] [13]
                ? // [14-15]
                    ( x >=  100000000000000ul // [15] [14]
                    ?   15
                    :   14
                    )
                : 13
                )
            :   // [11-12]
                ( x >=  100000000000ul // [12] [11]
                ?   12
                :   11
                )
            )
        )
    :   // [1-10]
        ( x >= 100000ul // [6-10] [1-5]
        ?   // [6-10]
            ( x >= 10000000ul // [8-10] [6-7]
            ?   // [8-10]
                ( x >= 100000000ul // [9-10] [8]
                ? // [9-10]
                    ( x >=  1000000000ul // [10] [9]
                    ?   10
                    :    9
                    )
                : 8
                )
            :   // [6-7]
                ( x >=  1000000ul // [7] [6]
                ?   7
                :   6
                )
            )
        :   // [1-5]
            ( x >= 100ul // [3-5] [1-2]
            ?   // [3-5]
                ( x >= 1000ul // [4-5] [3]
                ? // [4-5]
                    ( x >=  10000ul // [5] [4]
                    ?   5
                    :   4
                    )
                : 3
                )
            :   // [1-2]
                ( x >=  10ul // [2] [1]
                ?   2
                :   1
                )
            )
        )
    );
}

Für die Ganzzahl 'X' möchten Sie die Anzahl der Stellen wissen. In Ordnung, ohne eine Schleife zu verwenden. Diese Lösung wird nur in einer Formel in einer Zeile angezeigt. Dies ist also die optimalste Lösung, die ich je für dieses Problem gesehen habe.

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

int numberOfDigits(int n){

    if(n<=9){
        return 1;
    }
    return 1 + numberOfDigits(n/10);
}

Dies ist, was ich tun würde, wenn Sie es für Basis 10 wollen. Es ist ziemlich schnell und Sie werden wahrscheinlich keinen Stapel-Überlauf bekommen, wenn Sie ganze Zahlen zählen

int num,dig_quant = 0;
cout<<"\n\n\t\t--Count the digits in Number--\n\n";
cout<<"Enter Number: ";
cin>>num;
for(int i = 1; i<=num; i*=10){
    if(num / i  > 0){
      dig_quant += 1;
    }
}
 cout<<"\n"<<number<<" include "<<dig_quant<<" digit"
 cout<<"\n\nGoodbye...\n\n";

Wenn schneller effizienter ist, ist dies eine Verbesserung gegenüber der Verbesserung von andrei alexandrescu . Seine Version war bereits schneller als der naive Weg (dividiert durch 10 bei jeder Ziffer). Die folgende Version ist zeitlich konstant und zumindest auf x86-64 und ARM für alle Größen schneller, belegt jedoch doppelt so viel Binärcode, sodass sie nicht so cachefreundlich ist.

Benchmarks für diese Version vs alexandrescus Version auf meiner PR auf Facebook Torheit .

Funktioniert unsignednicht signed.

inline uint32_t digits10(uint64_t v) {
  return  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)
        + (std::uint32_t)(v>=1000000)
        + (std::uint32_t)(v>=10000000)
        + (std::uint32_t)(v>=100000000)
        + (std::uint32_t)(v>=1000000000)
        + (std::uint32_t)(v>=10000000000ull)
        + (std::uint32_t)(v>=100000000000ull)
        + (std::uint32_t)(v>=1000000000000ull)
        + (std::uint32_t)(v>=10000000000000ull)
        + (std::uint32_t)(v>=100000000000000ull)
        + (std::uint32_t)(v>=1000000000000000ull)
        + (std::uint32_t)(v>=10000000000000000ull)
        + (std::uint32_t)(v>=100000000000000000ull)
        + (std::uint32_t)(v>=1000000000000000000ull)
        + (std::uint32_t)(v>=10000000000000000000ull);
}

Ich arbeitete an einem Programm, bei dem ich überprüfen musste, ob der Benutzer richtig geantwortet hatte, wie viele Ziffern in einer Zahl enthalten waren. Daher musste ich eine Methode entwickeln, um die Anzahl der Ziffern in einer Ganzzahl zu überprüfen. Es war relativ einfach zu lösen.

double check=0, exponent=1000;

while(check<=1)
{
    check=number/pow(10, exponent);
    exponent--;
}

exponent=exponent+2;
cout<<exponent<<endl;

Dies war meine Antwort, die derzeit mit Zahlen mit weniger als 10 ^ 1000 Stellen funktioniert (kann durch Ändern des Exponentenwerts geändert werden).

PS Ich weiß, dass diese Antwort zehn Jahre zu spät ist, aber ich bin 2020 hierher gekommen, damit andere Leute sie verwenden können.

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

wo in haben powers_and_maxwir (10^n)-1für alle nsolche

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

und std::numeric_limits<type>::max()in einem 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());
   }
};

Hier ist ein einfacher 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);

Natürlich könnte jede andere Implementierung eines geordneten Satzes verwendet werden, powers_and_maxund wenn bekannt wäre, dass es Clustering geben würde, aber keine Kenntnis darüber, wo sich der Cluster möglicherweise befindet, ist möglicherweise eine selbstanpassende Baumimplementierung am besten

effektiver Weg

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

C ++ 11 Update der bevorzugten Lösung:

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

verhindert die Instanziierung von Vorlagen mit double et al. al.

int numberOfDigits(double number){
    if(number < 0){
        number*=-1;
    }
    int i=0;
        while(number > pow(10, i))
            i++;    
    cout << "This number has " << i << " digits" << endl;
    return i;
}

Dies ist mein Weg, um das zu tun:

   int digitcount(int n)
    {
        int count = 1;
        int temp = n;
        while (true)
        {
            temp /= 10;
            if (temp != 0) ++count;
            if (temp == 0) break;
        }

        return count;
    }

Hier ist ein anderer Ansatz:

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

Dies ist möglicherweise nicht effizient, nur etwas anderes als das, was andere vorgeschlagen haben.