Effiziente Methode zur Bestimmung der Anzahl von Ziffern in einer Ganzzahl

144

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

Seth
quelle
11
In welcher Basis? 2? 10?
Jacob Krall
2
Ich würde es gerne in Basis 10 machen
Seth
1
Ich habe einmal eine verwandte Frage gestellt: Wie kann man die erste Ziffer in einem int bekommen? Viele der gleichen Methoden wie unten wurden in den Antworten der Menschen verwendet. Hier ist der Link für den Fall, dass er für Ihre Aufgabe relevant ist [ stackoverflow.com/questions/701322/]
Dinah
Qualifiziert sich die Inline-Montage?
György Andrasek
1
Während sich alle diese Antworten auf Basis 10 beziehen, ist es ziemlich einfach zu ändern, um das Ergebnis für jede gewünschte Basis zu berechnen.
Ira Baxter

Antworten:

106

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];
}
Vitali
quelle
5
Wahrscheinlich schneller als meine Antwort, gut gemacht. Wenn Sie für zusätzliche Effizienz wissen, dass Ihre Eingangszahlen meistens klein sind (ich schätze weniger als 100.000), kehren Sie die Tests um: if (x <10) return 1; wenn (x <100) 2 zurückgibt; usw., so dass die Funktion weniger Tests durchführt und schneller beendet wird.
Squelart
29
Oder ordnen Sie die if-Anweisungen neu an und verschachteln Sie sie, um eine binäre Suche anstelle einer linearen Suche durchzuführen.
Dave4420
1
Das ist keine gute Idee. Was passiert, wenn die Architektur auf 256-Bit-Ganzzahlen erweitert wird? Sie müssen daran denken, diesen Code erneut zu ändern. Im wirklichen Leben wird dies nicht passieren, und dies wird wahrscheinlich verwendet, um einen Puffer mit der richtigen Größe zu erstellen, den Sie jetzt für alle Arten von Puffer-Over-Run-Problemen bei größeren Architekten öffnen.
Martin York
3
Unter der Annahme einer gleichmäßigen Verteilung der Zahlen kann die umgekehrte lineare Suche (von maximal bis 1) im Durchschnitt schneller sein als die binäre Suche, da es mit N Ziffern viel mehr Zahlen gibt als mit N-1 Ziffern graphics.stanford.edu/~ Seander /…
fa.
6
Ich würde mir keine Sorgen um 256- oder 128-Bit-Ganzzahlen machen. Wenn Sie nicht die Anzahl der Elektronen im Universum zählen müssen (10 ^ 78, als ich es das letzte Mal getan habe), sind 64 Bit ziemlich gut. 32-Bit-Maschinen haben ~ ~ 15 Jahre gedauert. Ich würde vermuten, dass 64-Bit-Maschinen viel länger halten. Für größere Zahlen ist die Multipräzisionsarithmetik in Ordnung, und ich bezweifle, dass die Effizienz der Berechnung der Ziffernzahl von Bedeutung ist.
Ira Baxter
74

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.

Skizz
quelle
7
Für 32-Bit-Ints und 56-Bit-Floats funktioniert dies wahrscheinlich. Wenn die Eingabe lang ist (64 Bit), können die 56 Bit des Protokolls mit doppelter Genauigkeit dazu führen, dass dies bei Werten nahe großen Werten von 10 ^ n zu einer falschen Antwort führt. Erwarten Sie Probleme über 2 ^ 50.
Ira Baxter
1
Es stellt sich auch die Frage, wie genau die Protokollfunktionen sind. Ich habe nicht überprüft, wie genau sie in modernen Bibliotheken sind, und würde nicht gerne blind darauf vertrauen, dass sie zu einem Teil einer Milliarde gut sind.
David Thornley
@DavidThornley: Protokoll- oder andere mathematische Funktionen sind absolut präzise, ​​sofern sie nicht in der Compiler-Befehlszeile angegeben sind. Einige werden zur Kompilierungszeit in x86-Intrinsics konvertiert. Einige existieren nicht und werden sich zu Formeln bestehender Intrinsics erweitern. Wenn -fpfastSie beispielsweise verwenden, können Sie die Verwendung von SSE-Instrumenten anstelle von x87 sehen, was weniger Garantie für die Präzision IIRC bietet. aber standardmäßig kein problem.
v.oddou
@ DavidThornley: Es ist mehr als Präzision. Die Frage ist, ob garantiert ist, dass log10 (10 ^ k) ≥ k für alle relevanten k ist oder nicht. Das heißt, es ist garantiert, dass jeder unvermeidliche Rundungsfehler in die richtige Richtung geht. k + eps funktioniert daher, k - eps nicht. Und "Perfekt präzise" ist naiv.
gnasher729
1
Der Test i> 0 konnte auf i> 9
Pat
60

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)))))))));  
}  
Brad
quelle
29
Und ich wäre nicht überrascht, wenn diese Lösung die schnellste sein würde.
VisioN
32
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 ...

Squelart
quelle
3
Dies kann schneller sein oder auch nicht als der von mir gewählte Ansatz der ungerollten Schleife - Sie müssten den Unterschied profilieren (sollte auf lange Sicht vernachlässigbar sein).
Vitali
Einverstanden, Profiling ist der einzige Weg, um wirklich sicher zu wissen! Ich habe meine Antwort mit diesem Kommentar aktualisiert, da die Antwort von Ben S für Ceil (log10 ()) verschwunden ist.
Squelart
11

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.

blinnov.com
quelle
4
Erstens funktioniert Ihre Lösung für 0 nicht. Zweitens ist Ihre Lösung nicht auf den allgemeinen Fall einer Variablen anwendbar. Drittens, wenn Sie ein konstantes Literal verwenden, wissen Sie bereits, wie viele Ziffern es hat.
Vitali
Es funktioniert auch für 0. Es funktioniert auch für jede Basis. Der Rest sind gültige Punkte, die ich bereits skizziert habe.
blinnov.com
3
Ich glaube nicht, dass es tatsächlich so ist. Es schlägt auf 0und auch auf Basis fehl 1:) und gibt Division durch Null Fehler, wenn die Basis als gegeben ist 0. Es kann jedoch behoben werden. Wie auch immer, ich suche nicht nach einem sehr alten Beitrag, also tut mir leid, ich denke nur, dass dies kein Witz sein muss und tatsächlich nützlich sein könnte.
tjm
9

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.

Josh Haberman
quelle
Es ist unklar, ob das Bit-Twiddling tatsächlich schneller ist. Selbst im schlimmsten Fall erfordert mein modifizierter Ansatz 4 Vergleiche (möglicherweise kann ich ihn auf 3 reduzieren, wenn ich die Partitionierung weiter untersuche, obwohl dies unwahrscheinlich erscheint). Ich bezweifle ernsthaft, dass dies durch arithmetische Operationen + Speicherlasten übertroffen wird (obwohl diese bei ausreichendem Zugriff im CPU-Cache verschwinden). Denken Sie daran, dass sie in dem Beispiel, das sie geben, auch die Protokollbasis 2 als abstrakte IntegerLogBase2-Funktion ausblenden (was selbst eigentlich nicht billig ist).
Vitali
Ja, wenn die Nummern normal verteilt sind, ist die Überprüfung der Reihenfolge schneller. Es hat jedoch den entarteten Fall, im schlimmsten Fall doppelt so langsam zu sein. Der nach Anzahl der Ziffern anstelle des Eingabebereichs partitionierte Ansatz bedeutet, dass das Verhalten keinen entarteten Fall aufweist und immer eine optimale Leistung erbringt. Denken Sie außerdem daran, dass Sie davon ausgehen, dass die Zahlen gleichmäßig verteilt sind. Tatsächlich folgen sie eher einer Verteilung im Zusammenhang mit <a href=" en.wikipedia.org/wiki/…> , wie ich vermute.
Vitali
Die Bit-Twiddling-Hacks sind nicht schneller als die oben beschriebene Partitionsmethode, aber sie sind möglicherweise interessant, wenn Sie hier einen allgemeineren Fall wie einen Float hatten.
Corwin Joy
1
Das Bit Twiddling Hacks schlägt einen Weg vor, um das int log10 zu erhalten, wenn das int log2 gegeben ist. Es werden verschiedene Möglichkeiten vorgeschlagen, um int log2 zu erhalten, wobei meist nur wenige Vergleiche / Verzweigungen erforderlich sind. (Ich denke, Sie unterschätzen die Kosten für unvorhersehbare Filialen, Vitali). Wenn Sie Inline x86 asm verwenden können, gibt Ihnen der BSR-Befehl das int log2 eines Werts (dh den Bitindex eines höchstwertigen gesetzten Bits). Bei K8 (Latenz von 10 Zyklen) ist es etwas langsam, bei Core 2 (Latenz von 2 oder 3 Zyklen) jedoch schnell. Auch auf K8 kann durchaus schneller sein als die Vergleiche.
Peter Cordes
Auf K10 zählt lzcnt führende Nullen, daher ist es fast dasselbe wie bsr, aber eine Eingabe von 0 ist kein Sonderfall mehr mit undefinierten Ergebnissen. Latenzen: BSR: 4, LZCNT: 2.
Peter Cordes
8

In String konvertieren und dann integrierte Funktionen verwenden

unsigned int i;
cout<< to_string(i).length()<<endl;
Wugoat
quelle
7
int x = 1000;
int numberOfDigits = x ? static_cast<int>(log10(abs(x))) + 1 : 1;
bemaru
quelle
3
Dies ist zwar in Bezug auf LOCs effizient, wie in der akzeptierten Antwort angegeben, aber die Verwendung von Protokoll wird wahrscheinlich nicht die beste Leistung bringen.
Ian
@ Ian Warum nicht? Es sind nur ein paar FPU-Anweisungen. Meilen besser als alle Zweige und Schleifen in anderen Antworten.
Marquis von Lorne
5

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; }
Ira Baxter
quelle
1
Der Teufel steckt im Detail - was passiert mit sagen std :: numeric_limits <int> :: max == number - es könnte ein Problem beim Beenden geben
pgast
2
Wenn Sie sich über diesen Fall Sorgen machen, können Sie eine zusätzliche IF hinzufügen, um sehr große Werte zu verarbeiten.
Ira Baxter
2
Ich sollte beachten, dass auf x86-Maschinen eine Multiplikation mit einer Konstanten 10, wie sie in diesem Fall verwendet wird, vom Compiler tatsächlich als LEA R2, [8 * R1 + R1], ADD R1, R2 implementiert werden kann, sodass maximal 2 Takte benötigt werden. Multiplikationen mit Variablen dauern zehn Uhren, und Divisionen sind viel schlimmer.
Ira Baxter
Der Vorteil des Divide-Ansatzes besteht darin, dass Sie sich keine Gedanken über negative Zahlen machen müssen.
Johannes Schaub - litb
1
Ich habe den Multiplikationsansatz (mit einer Fabs, um das Vorzeichenproblem zu beseitigen) mit dem Divisionsansatz verglichen. Auf meiner Maschine ist der Divisionsansatz um Faktor 2 langsamer als der Multiplikationsansatz. Ob dies eine vorzeitige Optimierung ist oder nicht, hängt wirklich davon ab, wo und wie dies aufgerufen wird.
Spacemoose
5

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.


quelle
Diese Lösung berechnet log2 (15) = 4 Bit und log2 (9) = 4 Bit. Für 15 und 9 ist jedoch eine unterschiedliche Anzahl von Dezimalstellen zum Drucken erforderlich. Es funktioniert also nicht, es sei denn, es macht Ihnen nichts aus, wenn Ihre Zahlen manchmal mit zu vielen Ziffern gedruckt werden. In diesem Fall können Sie jedoch immer "10" als Antwort für int auswählen.
Ira Baxter
Wow, eine ungefähre Funktion. Nett.
Doug65536
4
 #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.

RoryHector
quelle
1

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.

janm
quelle
Sie möchten, dass die Prüfung der Obergrenze zuerst als separate Bedingung getestet wird, damit Sie sie nicht bei jeder Schleifeniteration überprüfen.
Ira Baxter
Sie möchten nicht 10 in diese Temperatur t setzen. Der Compiler könnte das Multiplizieren mit t als Multiplikation mit einer reellen Variablen betrachten und einen Allzweck-Multiplikationsbefehl verwenden. Wenn Sie stattdessen "result * = 10;" Der Compiler wird sicherlich die Multiplikation mit der Konstanten 10 bemerken und diese mit ein paar Verschiebungen und Additionen implementieren, was extrem schnell ist.
Ira Baxter
Wenn die Multiplikation mit t immer eine Multiplikation mit 10 wäre, könnte der Compiler die Stärke reduzieren. In diesem Fall ist t jedoch nicht schleifeninvariant (es ist nur eine Modifikation einer ganzzahligen Potenzfunktion, die ich herumliegen hatte). Die richtige Optimierung ist die Spezialisierung auf den Typ, der eine Konstante zurückgibt. Sie haben jedoch Recht, dass in diesem Fall die Funktion immer 10 auf eine Potenz erhöht, nicht eine beliebige Ganzzahl auf eine Potenz, und eine Verringerung der Stärke einen guten Gewinn ergibt. Also habe ich eine Änderung vorgenommen ... Dieses Mal bleiben weitere Änderungen wirklich als Übung übrig! (Stapelüberlauf ist eine große
Zeitsenke
1
#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
            )
        )
    );
}
Adolfo
quelle
0

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.

Alexey Biryukov
quelle
0

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

JFS
quelle
0
// 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) );
Adolfo
quelle
Korrektur für "Praktischer Witz" von 'blinnov.com' oben
Adolfo
0
/// 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
                )
            )
        )
    );
}
Adolfo
quelle
0

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 ; 
Sameh Adel
quelle
Schlägt für INT_MAX und auch für negative Zahlen fehl.
Ranu
@ranu schlägt für INT_MAX fehl wie? Wann wird das Argument in konvertiert double? Oder beziehen Sie sich auf eine unmögliche Ganzzahleingabe mit INT_MAX-Dezimalstellen? Was würde hier auch bei jeder anderen Antwort scheitern?
Marquis von Lorne
0
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

Mc Stevens
quelle
0
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";
zwi3b3l404
quelle
0

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);
}
Gabriel
quelle
0

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.

Daniel Bercero
quelle
-1
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

pgast
quelle
-1

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;
}
Davit Siradeghyan
quelle
-1

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.

gerardw
quelle
-1
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;
}
DPenner1
quelle
-2

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;
    }
Leonardo Urbano
quelle
2
während True / Break-Syndrom: D
Петър Петров
-1 Dies ist der gleiche Ansatz, den die erste Antwort sechs Jahre zuvor gegeben hat, und er fügt nichts hinzu (tatsächlich ist er bedeutend schlechter).
-4

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.

Ashwin
quelle
4
Die Anfrage war äußerst effizient. Das ist das Gegenteil.
Ira Baxter