Wie bestimme ich die Anzahl der Ziffern einer Ganzzahl in C?

73

zum Beispiel,

n = 3432, result 4

n = 45, result 2

n = 33215, result 5

n = -357, result 3

Ich denke, ich könnte es einfach in eine Saite verwandeln und dann die Länge der Saite ermitteln, aber das scheint verworren und hackig zu sein.

c math willc2
quelle
6
Das Abrufen der Zeichenfolgenlänge würde bei negativen Zahlen fehlschlagen. Ermitteln Sie stattdessen die Länge des Absolutwerts. ;-)
Wim ten Brink
1
Char Buff [100]; int r = sprintf (Buff, "% s", n) - (r <0);
Paxdiablo
1
du meinst Dezimalstellen? Dezimalstellen sind per Definition reelle Zahlen und ganze Zahlen nicht.
Will
1
Äh ... Pax, ist das ein juristischer Ausdruck? Da r vor der Zuweisung keinen Wert hat, erscheint der Teil "(r <0)" beängstigend. Oder vielleicht meinten Sie, dass es als zweiter Schritt gemacht werden sollte, also ist es nur die Notation, die ich nicht bekomme (ich lese es, als wäre es C).
Entspannen Sie
3
Muss ... daran denken ... zu ... Einheit ... testen! Char Buff [100]; int r = sprintf (Buff, "% d", n) - (n <0);
paxdiablo

Antworten:

104 
floor (log10 (abs (x))) + 1

http://en.wikipedia.org/wiki/Logarithm

nervös
quelle
22
Nicht wenn x Null ist.
Finnw
10
Dies wäre unnötig langsam. Verwenden Sie keine teuren Funktionen wie log10 () ohne Grund. Die schnelle Ganzzahlfunktion ist einfach genug, um sie zu schreiben.
Sturmseele
30
Meine Güte ... laufen Sie noch einen 8088? Wer kümmert sich um ein paar zusätzliche Taktzyklen. Paz brauchte 100.000.000 Iterationen, um einen messbaren Unterschied zu machen, und selbst das war vernachlässigbar! 6 Sekunden! Whoop-dee-do .. mach weiter mit deinem Leben. Nächstes Jahr sind es 3 Sekunden.
Eduffy
7
@eduffy: Eine Millisekunde hier, eine Millisekunde dort ... und plötzlich spürt der Benutzer eine spürbare Verzögerung, nachdem er auf eine Schaltfläche geklickt hat. Im Ernst, diese kleinen Ineffizienzen summieren sich. Warum Taktzyklen verschwenden, wenn Sie dadurch nichts gewinnen?
Sturmseele
9
Es stellt sich heraus, dass die einfache Division für kleine Werte zwar schneller ist, der Logarithmus jedoch viel besser skaliert. Wenn Sie die Divisionsalgorithmen mit jedem int von MIN_INT bis MAX_INT aufrufen (und dies 100 m lang wiederholen wie in den Beispielen von Paz), erhalten Sie durchschnittlich 13,337 Sekunden pro Aufruf. Dasselbe mit Logarithmus zu tun, dauert durchschnittlich 8,143 Sekunden, die Rekursion dauert 11,971 Sekunden und die kaskadierenden If-Anweisungen dauern durchschnittlich 0,953 Sekunden. Die Daily-WTF-Lösung ist also eine Größenordnung schneller, aber auf lange Sicht liegt sie an zweiter Stelle.
Matt Poush
138

Der rekursive Ansatz :-)

int numPlaces (int n) {
    if (n < 0) return numPlaces ((n == INT_MIN) ? MAX_INT: -n);
    if (n < 10) return 1;
    return 1 + numPlaces (n / 10);
}

Oder iterativ:

int numPlaces (int n) {
    int r = 1;
    if (n < 0) n = (n == INT_MIN) ? INT_MAX: -n;
    while (n > 9) {
        n /= 10;
        r++;
    }
    return r;
}

Oder rohe Geschwindigkeit:

int numPlaces (int n) {
    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
    if (n < 10) return 1;
    if (n < 100) return 2;
    if (n < 1000) return 3;
    if (n < 10000) return 4;
    if (n < 100000) return 5;
    if (n < 1000000) return 6;
    if (n < 10000000) return 7;
    if (n < 100000000) return 8;
    if (n < 1000000000) return 9;
    /*      2147483647 is 2^31-1 - add more ifs as needed
       and adjust this final return as well. */
    return 10;
}

Die oben genannten wurden geändert, um MININT besser verarbeiten zu können. Auf seltsamen Systemen, die den sinnvollen 2 n 2-Komplementregeln für ganze Zahlen nicht folgen , müssen sie möglicherweise weiter angepasst werden.

Die Rohgeschwindigkeitsversion übertrifft tatsächlich die unten modifizierte Gleitkommaversion:

int numPlaces (int n) {
    if (n == 0) return 1;
    return floor (log10 (abs (n))) + 1;
}

Mit hundert Millionen Iterationen erhalte ich folgende Ergebnisse:

Raw speed with 0:            0 seconds
Raw speed with 2^31-1:       1 second
Iterative with 2^31-1:       5 seconds
Recursive with 2^31-1:       6 seconds
Floating point with 1:       6 seconds
Floating point with 2^31-1:  7 seconds

Das hat mich tatsächlich ein wenig überrascht - ich dachte, die Intel-Chips hätten eine anständige FPU, aber ich denke, allgemeine FP-Operationen können immer noch nicht mit handoptimiertem Integer-Code konkurrieren.

Aktualisieren Sie die folgenden Vorschläge von Stormsoul:

Das Testen der mehrfach iterativen Lösung mit Stormsoul ergibt ein Ergebnis von 4 Sekunden. Sie ist zwar viel schneller als die iterative Divide-Lösung, entspricht jedoch immer noch nicht der optimierten if-Anweisung-Lösung.

Durch die Auswahl der Argumente aus einem Pool von 1000 zufällig generierten Zahlen wurde die Geschwindigkeit der Rohgeschwindigkeit auf 2 Sekunden verkürzt. Obwohl es den Anschein hat, dass es jedes Mal von Vorteil war, jedes Mal dasselbe Argument zu haben, ist dies immer noch der schnellste Ansatz.

Das Kompilieren mit -O2 verbesserte die Geschwindigkeit, aber nicht die relativen Positionen (ich habe die Iterationszahl um den Faktor zehn erhöht, um dies zu überprüfen).

Jede weitere Analyse muss sich ernsthaft mit dem Innenleben der CPU-Effizienz befassen (verschiedene Arten der Optimierung, Verwendung von Caches, Verzweigungsvorhersage, welche CPU Sie tatsächlich haben, die Umgebungstemperatur im Raum usw.) störe meine bezahlte Arbeit :-). Es war eine interessante Ablenkung, aber irgendwann wird der Return on Investment für die Optimierung zu gering, um eine Rolle zu spielen. Ich denke, wir haben genug Lösungen, um die Frage zu beantworten (schließlich ging es nicht um Geschwindigkeit).

Weiteres Update:

Dies ist meine letzte Aktualisierung dieser Antwort, sofern keine offensichtlichen Fehler auftreten, die nicht von der Architektur abhängen. Inspiriert von den tapferen Bemühungen von Stormsoul zu messen, veröffentliche ich mein Testprogramm (geändert gemäß dem eigenen Testprogramm von Stormsoul) zusammen mit einigen Beispielzahlen für alle in den Antworten hier gezeigten Methoden. Beachten Sie, dass dies auf einem bestimmten Computer geschieht. Ihr Kilometerstand kann je nach Ausführungsort variieren (weshalb ich den Testcode veröffentliche).

Mach damit, wie du willst:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <time.h>

#define numof(a) (sizeof(a) / sizeof(a[0]))

/* Random numbers and accuracy checks. */

static int rndnum[10000];
static int rt[numof(rndnum)];

/* All digit counting functions here. */

static int count_recur (int n) {
    if (n < 0) return count_recur ((n == INT_MIN) ? INT_MAX : -n);
    if (n < 10) return 1;
    return 1 + count_recur (n / 10);
}

static int count_diviter (int n) {
    int r = 1;
    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
    while (n > 9) {
        n /= 10;
        r++;
    }
    return r;
}

static int count_multiter (int n) {
    unsigned int num = abs(n);
    unsigned int x, i;
    for (x=10, i=1; ; x*=10, i++) {
        if (num < x)
            return i;
        if (x > INT_MAX/10)
            return i+1;
    }
}

static int count_ifs (int n) {
    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
    if (n < 10) return 1;
    if (n < 100) return 2;
    if (n < 1000) return 3;
    if (n < 10000) return 4;
    if (n < 100000) return 5;
    if (n < 1000000) return 6;
    if (n < 10000000) return 7;
    if (n < 100000000) return 8;
    if (n < 1000000000) return 9;
    /*      2147483647 is 2^31-1 - add more ifs as needed
    and adjust this final return as well. */
    return 10;
}

static int count_revifs (int n) {
    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
    if (n > 999999999) return 10;
    if (n > 99999999) return 9;
    if (n > 9999999) return 8;
    if (n > 999999) return 7;
    if (n > 99999) return 6;
    if (n > 9999) return 5;
    if (n > 999) return 4;
    if (n > 99) return 3;
    if (n > 9) return 2;
    return 1;
}

static int count_log10 (int n) {
    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
    if (n == 0) return 1;
    return floor (log10 (n)) + 1;
}

static int count_bchop (int n) {
    int r = 1;
    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
    if (n >= 100000000) {
        r += 8;
        n /= 100000000;
    }
    if (n >= 10000) {
        r += 4;
        n /= 10000;
    }
    if (n >= 100) {
        r += 2;
        n /= 100;
    }
    if (n >= 10)
        r++;

    return r;
}

/* Structure to control calling of functions. */

typedef struct {
    int (*fnptr)(int);
    char *desc;
} tFn;

static tFn fn[] = {
    NULL,                              NULL,
    count_recur,    "            recursive",
    count_diviter,  "     divide-iterative",
    count_multiter, "   multiply-iterative",
    count_ifs,      "        if-statements",
    count_revifs,   "reverse-if-statements",
    count_log10,    "               log-10",
    count_bchop,    "          binary chop",
};
static clock_t clk[numof (fn)];

int main (int c, char *v[]) {
    int i, j, k, r;
    int s = 1;

    /* Test code:
        printf ("%11d %d\n", INT_MIN, count_recur(INT_MIN));
        for (i = -1000000000; i != 0; i /= 10)
            printf ("%11d %d\n", i, count_recur(i));
        printf ("%11d %d\n", 0, count_recur(0));
        for (i = 1; i != 1000000000; i *= 10)
            printf ("%11d %d\n", i, count_recur(i));
        printf ("%11d %d\n", 1000000000, count_recur(1000000000));
        printf ("%11d %d\n", INT_MAX, count_recur(INT_MAX));
    /* */

    /* Randomize and create random pool of numbers. */

    srand (time (NULL));
    for (j = 0; j < numof (rndnum); j++) {
        rndnum[j] = s * rand();
        s = -s;
    }
    rndnum[0] = INT_MAX;
    rndnum[1] = INT_MIN;

    /* For testing. */
    for (k = 0; k < numof (rndnum); k++) {
        rt[k] = (fn[1].fnptr)(rndnum[k]);
    }

    /* Test each of the functions in turn. */

    clk[0] = clock();
    for (i = 1; i < numof (fn); i++) {
        for (j = 0; j < 10000; j++) {
            for (k = 0; k < numof (rndnum); k++) {
                r = (fn[i].fnptr)(rndnum[k]);
                /* Test code:
                    if (r != rt[k]) {
                        printf ("Mismatch error [%s] %d %d %d %d\n",
                            fn[i].desc, k, rndnum[k], rt[k], r);
                        return 1;
                    }
                /* */
            }
        }
        clk[i] = clock();
    }

    /* Print out results. */

    for (i = 1; i < numof (fn); i++) {
        printf ("Time for %s: %10d\n", fn[i].desc, (int)(clk[i] - clk[i-1]));
    }

    return 0;
}

Denken Sie daran, dass Sie sicherstellen müssen, dass Sie die richtige Befehlszeile zum Kompilieren verwenden. Insbesondere müssen Sie möglicherweise die Mathematikbibliothek explizit auflisten, um log10()arbeiten zu können. Die Kommandozeile, die ich unter Debian verwendet habe, war gcc -o testprog testprog.c -lm.

Und in Bezug auf die Ergebnisse ist hier die Rangliste für meine Umgebung :

Optimierungsstufe 0:

Time for reverse-if-statements:       1704
Time for         if-statements:       2296
Time for           binary chop:       2515
Time for    multiply-iterative:       5141
Time for      divide-iterative:       7375
Time for             recursive:      10469
Time for                log-10:      26953

Optimierungsstufe 3:

Time for         if-statements:       1047
Time for           binary chop:       1156
Time for reverse-if-statements:       1500
Time for    multiply-iterative:       2937
Time for      divide-iterative:       5391
Time for             recursive:       8875
Time for                log-10:      25438
paxdiablo
quelle
3
Die rekursive Version scheint mir die sauberste, einfachste und beste selbstdokumentierende Lösung zu sein.
4
@moogs, Sie können jede der in dieser oder einer anderen Antwort vorgestellten Lösungen verwenden. Der Geschwindigkeitstest war wirklich nur eine Seite (die außer Kontrolle geriet). Und auf jeden Fall steht Ihnen diese Zeit noch zur Verfügung - es ist nur meine Zeit, die möglicherweise hier verschwendet wurde. Sie können also die Früchte meiner Arbeit nach Belieben verwenden :-)
paxdiablo
3
Ein kleiner Leistungstipp: Wenn Sie wissen, dass ein Wert immer nicht negativ ist, verwenden Sie vorzeichenlose Typen. Sie sind etwas schneller zu multiplizieren und zu teilen. Der Compiler könnte für Sie erraten, dass eine Variable niemals negativ ist, und diese Optimierung automatisch durchführen, aber auch nicht. In komplexeren Situationen ist dies niemals der Fall.
Sturmseele
1
Richtig. Jemand im IRC hat einige Leistungstests durchgeführt, dann hat er unsigniert verwendet und er hat einen wirklich großen Schub gegeben. Ich fordere Sie auf, die Welt ohne Vorzeichen auszuprobieren! :)
Johannes Schaub - litb
1
Schöne Antwort =) Ich mag die Raw-Speed-Version, aber ich denke, sie kann durch binäre Verzweigung verbessert werden, um die Anzahl der Vergleiche im ungünstigsten Fall auf vier zu reduzieren (ohne Berücksichtigung des negativen Tests), offensichtlich auf Kosten der Lesbarkeit . Insofern kann man eine Version davon speziell auf den beabsichtigten Datenbereich abstimmen.
Reis
28

Die kürzeste Antwort: snprintf(0,0,"%+d",n)-1

R .. GitHub HÖREN SIE AUF, EIS ZU HELFEN
quelle
4
snprintfwith n=0speichert nichts und erlaubt einen Nullpufferzeiger; Der Rückgabewert ist die Anzahl der Zeichen, die geschrieben worden wären. Der +Modifikator wird verwendet, um ein Vorzeichen ( +oder -) zu drucken, auch wenn der Wert nicht negativ ist. Wenn Sie eins vom Ergebnis abziehen, wird das Vorzeichen nicht als Ziffer gezählt.
R .. GitHub STOP HELPING ICE
1
Aus meiner (Debian Linux) Systems man-page auf snprintf: „ In Bezug auf den Rückgabewert snprintf(), SUSv2 und C99 einander widersprechen: wenn snprintf()mit genannt wird size=0[Größe ist das zweite Argument oben] dann SUSv2 sieht vor , nicht näher bezeichnet Rückgabewert kleiner als 1, während C99 erlaubt str in diesem Fall, NULL zu sein, und gibt den Rückgabewert (wie immer) als die Anzahl der Zeichen an, die geschrieben worden wären, wenn die Ausgabezeichenfolge groß genug gewesen wäre. " {SUS = Single UNIX Specification}
SlySven
5
@SlySven: SUSv2 ist uralt und irrelevant.
R .. GitHub STOP HELPING ICE
Nun, Debian ist dafür bekannt, etwas konservativ zu sein und nicht der Schnellste zu sein, der neue Sachen an Bord nimmt. 8-P Vielen Dank für Ihre Antwort - ich habe es in einem FOSS-Projekt verwendet, für das ich codiere (und habe es hier entsprechend zugeordnet) ...!
SlySven
1
@SlySven: Das kommt nicht von Debian AFAIK, sondern nur vom Linux-Manpages-Projekt. Ich glaube nicht, dass es jemals eine Linux-Bibliothek mit falschem snprintfVerhalten gegeben hat, aber es gab möglicherweise einige alte proprietäre Unices, und MSVCs _snprintfhatten auch den Fehler.
R .. GitHub STOP HELPING ICE
26

Pseudoalgorithmus für die binäre Suche, um keine der Ziffern von r in v zu erhalten.

if (v < 0 ) v=-v;

r=1;

if (v >= 100000000)
{
  r+=8;
  v/=100000000;
}

if (v >= 10000) {
    r+=4;
    v/=10000;
}

if (v >= 100) {
    r+=2;
    v/=100;
}

if( v>=10)
{
    r+=1;
}

return r;
Lakshmanaraj
quelle
4
Warum das Downvote, das sieht noch effizienter aus als die durch zehn geteilten Schleifen?
Paxdiablo
1
Downvote war nicht von mir, aber ich vermute, es war, weil dies weniger lesbar ist als Wayne Shephards Variation (und wahrscheinlich langsamer).
Brian
5
Ich verstehe, aber ich denke nicht, dass es richtig ist, etwas als weniger hilfreich abzustimmen - das Popup sagt eindeutig "Diese Antwort ist nicht hilfreich". In diesem Fall würde ich den anderen positiv bewerten und diesen in Ruhe lassen. Dies war eine echte Verbesserung gegenüber der / 10-Iteration. Trotzdem ist es jetzt positiv, also kein Schaden, kein Foul. (Dies ist nicht an dich gerichtet, Brian, da du es, wie du bereits gesagt hast, nicht getan hast). Nur Denkanstöße für jeden, der es getan hat.
paxdiablo
5
Mein Algorithmus kann leicht für lange Variablen erweitert werden, indem am Anfang eine andere if-Anweisung steht, wenn (v> = 10000000000000000LL) {r + = 16; v / = 10000000000000000LL; } und wird schneller sein als alle Ansätze.
Lakshmanaraj
8

Teilen Sie in einer Schleife durch 10, bis das Ergebnis Null erreicht. Die Anzahl der Iterationen entspricht der Anzahl der Dezimalstellen.

Angenommen, Sie erwarten 0 Stellen in einem Nullwert:

int countDigits( int value )
{
    int result = 0;
    while( value != 0 ) {
       value /= 10;
       result++;
    }
    return result;
}
scharfer Zahn
quelle
Boden (log10 (abs (x))) + 1 wäre schneller, aber eduffy hat das bereits vorgeschlagen! :-)
Wim ten Brink
Ich wäre gespannt auf das Timing. Ich würde fast denken, dass eine optimierte Reihe von if-Anweisungen (basierend auf maxint) einen Gleitkomma-Logarithmus übertreffen könnte (aber ich bin zu faul, um ihn selbst zu testen).
Paxdiablo
Es wird niemals Null erreichen, oder?
@ John Pirie: Warum sollte es nicht? Ich meine Ganzzahldivision und wenn sie iterativ auf dieselbe Variable angewendet wird, ergibt sie schließlich Null.
Scharfzahn
@JP, wenn Sie eine ganze Zahl durch 10 teilen, wird sie schließlich Null erreichen.
Paxdiablo
7

Sie können Folgendes tun: floor (log10 (abs (x))) + 1 Wenn Sie Zyklen sparen möchten, können Sie auch Vergleiche durchführen

if(x<10)
  return 1;
if(x<100)
  return 2;
if(x<1000)
  return 3;
etc etc

Dies vermeidet rechenintensive Funktionen wie Log oder sogar Multiplikation oder Division. Während es unelegant ist, kann dies ausgeblendet werden, indem es in eine Funktion eingekapselt wird. Es ist nicht komplex oder schwierig zu warten, daher würde ich diesen Ansatz wegen der schlechten Codierungspraxis nicht ablehnen. Ich habe das Gefühl, das Baby mit dem Badewasser rauszuwerfen.

Howard May
quelle
1
oder ich könnte einfach ein Dialogfeld
öffnen
2
Und warum die Abstimmung hier? Dies stellt sich als unglaublich schnell heraus.
Paxdiablo
Die Protokollfunktion müsste ziemlich schlecht sein, wenn diese Lösung für den allgemeinen Fall schneller ist
David Cournapeau
2
@ David: Logarithmen dauern je nach CPU zwischen 250 und 700 Zyklen. Selbst wenn Sie sich vorstellen, dass jeder Zweig in dieser Antwort 25 Zyklen dauert, benötigen Sie 10 bis 30 Stellen, bevor er langsamer als ein Logarithmus wird, und das ist der schlimmste Fall. Wenn Ihre typischen Zahlen klein sind, ist es noch besser.
R .. GitHub STOP HELPING ICE
7

Konstantkostenversion mit x86-Assembly und Nachschlagetabelle:

int count_bsr(int i) {
    struct {
            int max;
            int count;
    } static digits[32] = {
            { 9, 1 }, { 9, 1 }, { 9, 1 }, { 9, 1 },
            { 99, 2 }, { 99, 2 }, { 99, 2 },
            { 999, 3 }, { 999, 3 }, { 999, 3 },
            { 9999, 4 }, { 9999, 4 }, { 9999, 4 }, { 9999, 4 },
            { 99999, 5 }, { 99999, 5 }, { 99999, 5 },
            { 999999, 6 }, { 999999, 6 }, { 999999, 6 },
            { 9999999, 7 }, { 9999999, 7 }, { 9999999, 7 }, { 9999999, 7 },
            { 99999999, 8 }, { 99999999, 8 }, { 99999999, 8 },
            { 999999999, 9 }, { 999999999, 9 }, { 999999999, 9 },
            { INT_MAX, 10 }, { INT_MAX, 10 }
    };
        register const int z = 0;
        register unsigned log2;
        if (i < 0) i = -i;
        __asm__ __volatile__ (
                "bsr %1, %0;"  \
                "cmovz %2, %0;"\
                : "=r" (log2)  \
                : "rm" (i), "r"(z));
        return digits[log2].count + ( i > digits[log2].max );
}

Eine andere mit einer kleineren Nachschlagetabelle und einer log10-Näherung von hier .

int count_bsr2( int i ) {
    static const unsigned limits[] =
            {0, 10, 100, 1000, 10000, 100000,
             1000000, 10000000, 100000000, 1000000000};
        register const int z = 0;
        register int l, log2;
        if (i < 0) i = -i;
        __asm__ __volatile__ (
                "bsr %1, %0;"  \
                "cmovz %2, %0;"\
                : "=r" (log2)  \
                : "rm" (i), "r"(z));
       l = (log2 + 1) * 1233 >> 12;
       return (l + ((unsigned)i >= limits[l]));
}

Beide nutzen die Tatsache, dass auf x86 -INT_MIN gleich INT_MIN ist.

Aktualisieren:

Gemäß dem Vorschlag hier sind die Timings für die count_bsr- und eine etwas schnellere 64-Bit- Routine count_bsr_mod im Vergleich zu den binären Such- und binären Chop-Algen unter Verwendung des Testprogramms von paxdiablo, das so modifiziert ist, dass Sätze mit einer zufälligen Vorzeichenverteilung erzeugt werden. Die Tests wurden mit gcc 4.9.2 unter Verwendung der Optionen "-O3 -falign-functions = 16 -falign-jumps = 16 -march = corei7-avx" erstellt und auf einem ansonsten ruhenden Sandy Bridge-System mit ausgeschaltetem Turbo- und Schlafzustand ausgeführt.

Zeit für bsr mod: 270000  
Zeit für bsr: 340000  
Zeit für binären Chop: 800000  
Zeit für die binäre Suche: 770000  
Zeit für den binären Suchmod: 470000

Quelle für den Test,

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <time.h>

#define numof(a) (sizeof(a) / sizeof(a[0]))

/* Random numbers and accuracy checks. */

static int rndnum[10000];
static int rt[numof(rndnum)];

/* All digit counting functions here. */

static int count_bchop (int n) {
    int r = 1;
    if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
    if (n >= 100000000) {
        r += 8;
        n /= 100000000;
    }
    if (n >= 10000) {
        r += 4;
        n /= 10000;
    }
    if (n >= 100) {
        r += 2;
        n /= 100;
    }
    if (n >= 10)
        r++;

    return r;
}

static int count_bsearch(int i)
{
    if (i < 0)
    {
        if (i == INT_MIN)
            return 11; // special case for -2^31 because 2^31 can't fit in a two's complement 32-bit integer
        i = -i;
    }
    if              (i < 100000) {
        if          (i < 1000) {
            if      (i < 10)         return 1;
            else if (i < 100)        return 2;
            else                     return 3;
        } else {
            if      (i < 10000)      return 4;
            else                     return 5;
        }
    } else {
        if          (i < 10000000) {
            if      (i < 1000000)    return 6;
            else                     return 7;
        } else {
            if      (i < 100000000)  return 8;
            else if (i < 1000000000) return 9;
            else                     return 10;
        }
    }
}

// Integer log base 10, modified binary search.
static int count_bsearch_mod(int i) {
   unsigned x = (i >= 0) ? i : -i;
   if (x > 99)
      if (x > 999999)
         if (x > 99999999)
            return 9 + (x > 999999999);
         else
            return 7 + (x > 9999999);
      else
         if (x > 9999)
            return 5 + (x > 99999);
         else
            return 3 + (x > 999);
   else
         return 1 + (x > 9);
}

static int count_bsr_mod(int i) {
    struct {
            int m_count;
            int m_threshold;
    } static digits[32] =
    {
      { 1, 9 }, { 1, 9 }, { 1, 9 }, { 1, 9 },
      { 2, 99 }, { 2, 99 }, { 2, 99 },
      { 3, 999 }, { 3, 999 }, { 3, 999 },
      { 4, 9999 }, { 4, 9999 }, { 4, 9999 }, { 4, 9999 },
      { 5, 99999 }, { 5, 99999 }, { 5, 99999 },
      { 6, 999999 }, { 6, 999999 }, { 6, 999999 },
      { 7, 9999999 }, { 7, 9999999 }, { 7, 9999999 }, { 7, 9999999 },
      { 8, 99999999 }, { 8, 99999999 }, { 8, 99999999 },
      { 9, 999999999 }, { 9, 999999999 }, { 9, 999999999 },
      { 10, INT_MAX }, { 10, INT_MAX }
    };
        __asm__ __volatile__ (
            "cdq                    \n\t"
            "xorl %%edx, %0         \n\t"
            "subl %%edx, %0         \n\t"
            "movl %0, %%edx         \n\t"
            "bsrl %0, %0            \n\t"
            "shlq $32, %%rdx        \n\t"
            "movq %P1(,%q0,8), %q0  \n\t"
            "cmpq %q0, %%rdx        \n\t"
            "setg %%dl              \n\t"
            "addl %%edx, %0         \n\t"
                : "+a"(i)
                : "i"(digits)
                : "rdx", "cc"
        );
    return i;
}

static int count_bsr(int i) {
    struct {
            int max;
            int count;
    } static digits[32] = {
            { 9, 1 }, { 9, 1 }, { 9, 1 }, { 9, 1 },
            { 99, 2 }, { 99, 2 }, { 99, 2 },
            { 999, 3 }, { 999, 3 }, { 999, 3 },
            { 9999, 4 }, { 9999, 4 }, { 9999, 4 }, { 9999, 4 },
            { 99999, 5 }, { 99999, 5 }, { 99999, 5 },
            { 999999, 6 }, { 999999, 6 }, { 999999, 6 },
            { 9999999, 7 }, { 9999999, 7 }, { 9999999, 7 }, { 9999999, 7 },
            { 99999999, 8 }, { 99999999, 8 }, { 99999999, 8 },
            { 999999999, 9 }, { 999999999, 9 }, { 999999999, 9 },
            { INT_MAX, 10 }, { INT_MAX, 10 }
    };
        register const int z = 0;
        register unsigned log2;
        if (i < 0) i = -i;
        __asm__ __volatile__ (
                "bsr %1, %0;"  \
                "cmovz %2, %0;"\
                : "=r" (log2)  \
                : "rm" (i), "r"(z));
        return digits[log2].count + ( i > digits[log2].max );
}

/* Structure to control calling of functions. */

typedef struct {
    int (*fnptr)(int);
    const char *desc;
} tFn;

static tFn fn[] = {
 {   NULL,                              NULL },
 {   count_bsr_mod,  "              bsr mod" },
 {   count_bsr,      "                  bsr" },
 {   count_bchop,    "          binary chop" },
 {   count_bsearch,  "        binary search" },
 {   count_bsearch_mod,"    binary search mod"}
};
static clock_t clk[numof (fn)];

int main (int c, char *v[]) {
    int i, j, k, r;
    int s = 1;

    /* Test code:
        printf ("%11d %d\n", INT_MIN, count_bsearch(INT_MIN));
        //for (i = -1000000000; i != 0; i /= 10)
        for (i = -999999999; i != 0; i /= 10)
            printf ("%11d %d\n", i, count_bsearch(i));
        printf ("%11d %d\n", 0, count_bsearch(0));
        for (i = 1; i != 1000000000; i *= 10)
            printf ("%11d %d\n", i, count_bsearch(i));
        printf ("%11d %d\n", 1000000000, count_bsearch(1000000000));
        printf ("%11d %d\n", INT_MAX, count_bsearch(INT_MAX));
    return 0;
    /* */

    /* Randomize and create random pool of numbers. */

    int p, n;
    p = n = 0;
    srand (time (NULL));
    for (j = 0; j < numof (rndnum); j++) {
        rndnum[j] = ((rand() & 2) - 1) * rand();
    }
    rndnum[0] = INT_MAX;
    rndnum[1] = INT_MIN;

    /* For testing. */
    for (k = 0; k < numof (rndnum); k++) {
        rt[k] = (fn[1].fnptr)(rndnum[k]);
    }

    /* Test each of the functions in turn. */

    clk[0] = clock();
    for (i = 1; i < numof (fn); i++) {
        for (j = 0; j < 10000; j++) {
            for (k = 0; k < numof (rndnum); k++) {
                r = (fn[i].fnptr)(rndnum[k]);
                /* Test code:
                    if (r != rt[k]) {
                        printf ("Mismatch error [%s] %d %d %d %d\n",
                            fn[i].desc, k, rndnum[k], rt[k], r);
                        return 1;
                    }
                /* */
            }
        }
        clk[i] = clock();
    }

    /* Print out results. */

    for (i = 1; i < numof (fn); i++) {
        printf ("Time for %s: %10d\n", fn[i].desc, (int)(clk[i] - clk[i-1]));
    }

    return 0;
}
Alexander Korobka
quelle
1
+1 für die geekigste Antwort. Sie sollten Leistungsdaten hinzufügen, um zu zeigen, wie gut es funktioniert, insbesondere im Vergleich zu binärem Chop.
CodeManX
Es ist ein Fehler in count_bsearch(): Für die Semantik des OP, sollte es zurückgeben 10zu i == INT_MIN.
Chqrlie
7

Hier ist eine entrollte binäre Suche ohne Division oder Multiplikation. Abhängig von der Verteilung der ihm gegebenen Zahlen kann es die anderen mit ungerollten if-Anweisungen erstellten oder nicht übertreffen, sollte jedoch immer diejenigen schlagen, die Schleifen und Multiplikation / Division / log10 verwenden.

Bei einer gleichmäßigen Verteilung der Zufallszahlen über den gesamten Bereich betrug der Durchschnitt auf meinem Computer 79% der Ausführungszeit von count_bchop () von paxdiablo, 88% der Zeit von count_ifs () und 97% der Zeit von count_revifs ().

Bei einer Exponentialverteilung (die Wahrscheinlichkeit, dass eine Zahl n Stellen hat, ist gleich der Wahrscheinlichkeit , dass sie m Stellen hat, wobei m ≠ n ist ) schlagen count_ifs () und count_revifs () meine Funktion. Ich bin mir nicht sicher warum an dieser Stelle.

int count_bsearch(int i)
{
    if (i < 0)
    {
        if (i == INT_MIN)
            return 10; // special case for -2^31 because 2^31 can't fit in a two's complement 32-bit integer
        i = -i;
    }
    if              (i < 100000) {
        if          (i < 1000) {
            if      (i < 10)         return 1;
            else if (i < 100)        return 2;
            else                     return 3;
        } else {
            if      (i < 10000)      return 4;
            else                     return 5;
        }
    } else {
        if          (i < 10000000) {
            if      (i < 1000000)    return 6;
            else                     return 7;
        } else {
            if      (i < 100000000)  return 8;
            else if (i < 1000000000) return 9;
            else                     return 10;
        }
    }
}
Deadcode
quelle
1
Das ist lustig ... Ich habe kurz zuvor einen Kommentar dazu geschrieben, nachdem ich die 'Raw Speed'-Version in Paxdiablos Antwort gesehen hatte. Dann stellte ich fest, dass Sie diese Antwort etwa 15 Minuten zuvor geschrieben hatten. Na ja, +1 =) Beachten Sie, dass Sie die Grenzen ändern können, um die Leistung der Funktion zugunsten bestimmter Datenbereiche zu optimieren.
Reis
Du musst mich veräppeln! Was sind die Chancen? Alle anderen Antworten wurden vor über 3 Jahren veröffentlicht. Unsere Geschichten sind sogar ein bisschen ähnlich. Ich habe mit 8 Jahren angefangen, in BASIC auf einem IBM XT zu programmieren.
Deadcode
Ich habe mir die Liste "Aktive Beiträge" angesehen. Dies zeigte sich und sah interessant aus. Ich ging zu Paxdiablos Post, machte einen Kommentar und ging dann weg ... Kam später zurück und sah eine weitere Modifikation, so dass ich neugierig wurde. Es war deins. Denken Sie, wir sind gegenseitige Doppelgänger?
Paddy
Es ist ein Fehler in count_bsearch(): Für die Semantik des OP, sollte es zurückgeben 10zu i == INT_MIN.
Chqrlie
5

Ich bin bei einer Google-Suche darauf gestoßen: http://www.hackersdelight.org/hdcodetxt/ilog.c.txt

Ein schneller Benchmark zeigte deutlich, dass die binären Suchmethoden erfolgreich waren. lakshmanarajs Code ist ziemlich gut, Alexander Korobkas ist ~ 30% schneller, Deadcode ist noch ein kleines bisschen schneller (~ 10%), aber ich fand, dass die folgenden Tricks aus dem obigen Link eine weitere Verbesserung von 10% ergeben.

// Integer log base 10, modified binary search.
int ilog10c(unsigned x) {
   if (x > 99)
      if (x < 1000000)
         if (x < 10000)
            return 3 + ((int)(x - 1000) >> 31);
         // return 3 - ((x - 1000) >> 31);              // Alternative.
         // return 2 + ((999 - x) >> 31);               // Alternative.
         // return 2 + ((x + 2147482648) >> 31);        // Alternative.
         else
            return 5 + ((int)(x - 100000) >> 31);
      else
         if (x < 100000000)
            return 7 + ((int)(x - 10000000) >> 31);
         else
            return 9 + ((int)((x-1000000000)&~x) >> 31);
         // return 8 + (((x + 1147483648) | x) >> 31);  // Alternative.
   else
      if (x > 9)
            return 1;
      else
            return ((int)(x - 1) >> 31);
         // return ((int)(x - 1) >> 31) | ((unsigned)(9 - x) >> 31);  // Alt.
         // return (x > 9) + (x > 0) - 1;                             // Alt.
}

Beachten Sie, dass dies Protokoll 10 ist, nicht die Anzahl der Ziffern digits = ilog10c(x)+1 .

Unterstützt keine Negative, aber das lässt sich leicht mit a beheben -.

jozxyqk
quelle
3 
if (x == MININT) return 10;  //  abs(MININT) is not defined
x = abs (x);
if (x<10) return 1;
if (x<100) return 2;
if (x<1000) return 3;
if (x<10000) return 4;
if (x<100000) return 5;
if (x<1000000) return 6;
if (x<10000000) return 7;
if (x<100000000) return 8;
if (x<1000000000) return 9;
return 10; //max len for 32-bit integers

Sehr unelegant. Aber schneller als alle anderen Lösungen. Die Erstellung von Integer Division- und FP-Protokollen ist teuer. Wenn die Leistung kein Problem darstellt, ist die log10-Lösung mein Favorit.

Wayne Sheppard
quelle
Das stellt sich sogar im schlimmsten Fall als die schnellste Methode heraus (2 ^ 32-1) - siehe mein Update für Timings.
Paxdiablo
13
Ich vermute oft, dass "Codegeruch" ein Begriff ist, der von Leuten verwendet wird, die den Code einfach nicht mögen - es scheint ein sehr unwissenschaftlicher Begriff zu sein. Dieser Code ist perfekt lesbar (zumindest für mich und für alle anderen mit einem halben Gehirn, wenn Sie eine einfache Kommentarzeile hinzufügen) und übertrifft jede andere hier aufgeführte Lösung (sehr wichtig in der Umgebung, in der ich gefälscht wurde). Und der Algorithmus ist bei O (log n) skalierbar und portabel, wenn Sie nur weitere if-Anweisungen hinzufügen, um der Umgebung zu entsprechen, in der Sie arbeiten.
paxdiablo
2
Die Frage ist mit C und Mathe markiert. Jede Lösung ist willkommen, auch die schnellste.
Ben
@Pax: Wenn Sie es zu einer Schleife machen, sollte es nicht wesentlich langsamer werden (multiplizieren Sie den Schwellenwert wiederholt mit 10), und es wird kompakter. Als Bonus wäre es perfekt auf jede mögliche Größe von (int) portierbar, wenn Sie es durch MAX_INT oder ähnliches einschränken.
Sturmseele
2
Es ist schnell, weil es nur ein Vergleich pro Ziffer ist. Die iterativen Lösungen sind ein Vergleich, eine Division und ein Inkrement pro Ziffer. Die Ganzzahldivision ist teuer, 17 Zyklen auf einer C2D. log10 ist weit über 100 Zyklen.
Wayne Sheppard
2 
    int n = 437788;
    int N = 1; 
    while (n /= 10) N++;
xcramps
quelle
1
Funktioniert auch für negative Zahlen in Ordnung - teilt sich in einer Schleife, bis n Null wird, und dann stoppt die Schleife.
Scharfzahn
1
negiere es dann vorher, duh.
Künstlicher
Hier besteht keine Notwendigkeit zur Verneinung. Es wird iteriert, bis das Ergebnis gleich Null ist.
Scharfzahn
@sharptooth - aber der "End of Loop" -Test ist 10 nicht 0.
ChrisF
1
@ChrisF: Der End-of-Loop-Testausdruck in diesem Code ist ein ASSIGNMENT-Operator, kein Vergleich! Lesen Sie es wie folgt: while (n = n / 10, n! = 0) - Der letzte Ausdruck nach einem Komma ist der eigentliche End-of-Loop-Test.
Sturmseele
2

Nur ein wenig an die C-Sprache anpassen:

floor( log10( abs( (number)?number:1 ) ) + 1 );
Rafael Arturo Rocha Vidaurri
quelle
1

Ich weiß, dass ich zu spät komme, aber dieser Code ist + x10 schneller als alle anderen Antworten.

int digits(long long x)
{
    x < 0 ? x = -x : 0;
    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 :
        x < 10000000000 ? 10 : 0;
}

...

int x = -937810;
printf("%d : %d digits\n", x, digits(x));

Aus:

-937810 : 6 digits
Beyondo
quelle
0

Verwenden Sie KEINEN Boden (log10 (...)). Dies sind Gleitkommafunktionen und langsame Funktionen, die hinzugefügt werden müssen. Ich glaube, der schnellste Weg wäre diese Funktion:

int ilog10(int num)
{
   unsigned int num = abs(num);
   unsigned int x, i;
   for(x=10, i=1; ; x*=10, i++)
   {
      if(num < x)
         return i;
      if(x > INT_MAX/10)
         return i+1;
   }
}

Beachten Sie, dass die von einigen Leuten vorgeschlagene binäre Suchversion aufgrund von Verzweigungsfehlvorhersagen langsamer sein kann.

BEARBEITEN:

Ich habe einige Tests durchgeführt und einige wirklich interessante Ergebnisse erzielt. Ich habe meine Funktion zusammen mit allen von Pax getesteten Funktionen UND der von lakshmanaraj bereitgestellten binären Suchfunktion zeitlich festgelegt. Der Test wird mit dem folgenden Codefragment durchgeführt:

start = clock();
for(int i=0; i<10000; i++)
   for(int j=0; j<10000; j++)
      tested_func(numbers[j]);
end = clock();
tested_func_times[pass] = end-start;

Wobei das Array numbers [] zufällig generierte Zahlen über den gesamten Bereich des Typs int enthält (außer MIN_INT). Der Test wurde für jede getestete Funktion auf dem Array THE SAME numbers [] wiederholt. Der gesamte Test wurde zehnmal durchgeführt, wobei die Ergebnisse über alle Durchgänge gemittelt wurden. Der Code wurde mit GCC 4.3.2 mit der Optimierungsstufe -O3 kompiliert.

Hier sind die Ergebnisse:

floating-point log10:     10340ms
recursive divide:         3391ms
iterative divide:         2289ms
iterative multiplication: 1071ms
unrolled tests:           859ms
binary search:            539ms

Ich muss sagen, ich war wirklich erstaunt. Die binäre Suche lief weitaus besser als ich dachte. Ich habe überprüft, wie GCC diesen Code zu asm kompiliert hat. O_O. Jetzt ist das beeindruckend. Es wurde viel besser optimiert, als ich es für möglich hielt, und die meisten Zweige auf wirklich clevere Weise vermieden. Kein Wunder, dass es SCHNELL ist.

Sturmseele
quelle
Nun, der schnellste Weg ist das Abrollen dieser Schleife in handoptimierte if-Anweisungen. Aber Sie haben absolut Recht mit der Langsamkeit des Gleitkommas.
Paxdiablo
@Pax: Gleitkomma ist langsamer als Ganzzahl, und log10 () und floor () sind SEHR langsam. Ich bezog mich auf Letzteres.
Sturmseele
Ich werde dieses für die kluge Verwendung der Multiplikation auf der Schwelle anstatt der Division auf dem Wert stimmen. Ich nehme an, Sie könnten eine CPU erfinden, bei der die Teilung schneller war, aber ich glaube nicht, dass ich jemals eine gesehen habe, und ich würde wahrscheinlich den Ingenieur entlassen, der das getan hat :-)
paxdiablo
Lass es bei mir, @stormsoul, ich melde mich in ungefähr 8 Stunden bei dir (es ist Mitternacht hier in Oz).
Paxdiablo
@Pax: Das konntest du nicht. Die Divisionsoperation ist von Natur aus viel komplexer (und viel sequentieller ) als die Multiplikation - was jede Implementierung viel langsamer macht als dies mit Mults möglich ist. Ein optimierender Compiler würde übrigens keine Divisionen für den "Divisions" -Code ausgeben! Es würde es in eine Multiplikation durch Gegenseitigkeit umwandeln. Da der Divisor eine kleine Konstante ist, kann der Kehrwert zur Kompilierungszeit berechnet werden. Es würde auch keine Multiplikationen für den "Multiplikations" -Code ausgeben. Dies würde in zwei Schichten und eine Addition umgewandelt - für insgesamt 2 Taktzyklen.
Sturmseele
0

Mit dieser Formel Ceil (log10 (abs (x))) können Sie die Anzahl der Ziffern in einer Zahl ermitteln, wobei Ceil eine ganzzahlige Zahl zurückgibt, die nur größer als die Zahl ist

Anshul garg
quelle
0

Ich denke, der einfachste Weg wäre:

 int digits = 0;
if (number < 0) digits = 1;
while (number) {
    number /= 10;
    digits++;
}

Ziffern geben die Antwort.

Zeeshan
quelle
1
Diese Methode liefert falsche Ergebnisse (um eins) für negative ganze Zahlen, und in diesem Fall 0werden null Stellen gezählt.
jb
0

Ein einfacher Weg, um die Länge (dh die Anzahl der Stellen) der vorzeichenbehafteten Ganzzahl zu ermitteln, ist folgende:

while ( abs(n) > 9 )
{
    num /= 10;
    ++len;
}

Wo nist die Ganzzahl, deren Länge Sie ermitteln möchten, und wo lenentspricht die Anzahl der Stellen in der Ganzzahl? Dies funktioniert für beide Werte von n(negativ oder positiv).

Der Aufruf abs()ist optional, wenn Sie nur mit positiven Ganzzahlen arbeiten.


quelle
0

Für c # ist hier eine sehr schnelle und einfache Lösung ...

    private static int NumberOfPlaces(int n)
    {
       //fast way to get number of digits
       //converts to signed string with +/- intact then accounts for it by subtracting 1
       return n.ToString("+#;-#;+0").Length-1;
    }
neoscribe
quelle
-1 
void main()
{     
    int a,i;
    printf("Enter the number :");       
    scanf("%d",&a);

    while(a>0)     
    {
        a=a/10;   
        i++;  
    }

    getch();
}
Akshay
quelle