Skuteczny sposób na określenie liczby cyfr w liczbie całkowitej

144

Jaki jest bardzo skuteczny sposób określania liczby cyfr w liczbie całkowitej w C ++?

Seth
źródło
11
W jakiej bazie? 2? 10?
Jacob Krall
2
Chciałbym to zrobić w bazie 10
Seth
1
Kiedyś zadałem pokrewne pytanie: Jak uzyskać pierwszą cyfrę w int? W odpowiedziach ludzi używano wielu tych samych metodologii, co poniżej. Oto link na wypadek, gdyby dotyczyło Twojego zadania [ stackoverflow.com/questions/701322/]
Dinah,
Czy montaż na linii kwalifikuje się?
György Andrasek,
1
Chociaż wszystkie te odpowiedzi dotyczą podstawy 10, dość łatwo jest zmienić, aby obliczyć wynik dla dowolnej pożądanej podstawy.
Ira Baxter

Odpowiedzi:

106

Cóż, najbardziej wydajnym sposobem, zakładając, że znasz rozmiar liczby całkowitej, byłoby wyszukiwanie. Powinien być szybszy niż podejście oparte na znacznie krótszym logarytmie. Jeśli nie zależy ci na liczeniu „-”, usuń + 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
źródło
5
Prawdopodobnie szybciej niż moja odpowiedź, dobra robota. Dla zwiększenia wydajności, jeśli wiesz, że liczby wejściowe będą w większości małe (domyślam się, że mniej niż 100 000), odwróć testy: if (x <10) return 1; if (x <100) return 2; itp., aby funkcja wykonywała mniej testów i szybciej wychodziła.
squelart
29
A może zmień kolejność i zagnieżdżaj instrukcje if, aby wykonać wyszukiwanie binarne zamiast wyszukiwania liniowego.
dave4420
1
To nie jest dobry pomysł. Co się dzieje, gdy architektura rozszerza się do 256-bitowych liczb całkowitych. Musisz pamiętać, aby wrócić i zmodyfikować ten kod. W prawdziwym życiu to się nie wydarzy i prawdopodobnie zostanie to użyte do zbudowania bufora o odpowiednim rozmiarze, teraz otwierasz się na wszelkiego rodzaju problemy z uruchomieniem bufora w większych architekturach.
Martin York,
3
zakładając równomierny rozkład liczb, odwrotne wyszukiwanie liniowe (zaczynające się od maksymalnej liczby cyfr do 1) może być średnio szybsze niż wyszukiwanie binarne, ponieważ jest znacznie więcej liczb z N cyframi niż z grafiką
fa.
6
Nie martwiłbym się zbytnio o 256 lub 128 bitowe liczby całkowite. O ile nie musisz policzyć liczby elektronów we Wszechświecie (10 ^ 78, kiedy to zrobiłem), 64 bity będą całkiem nieźle. Maszyny 32-bitowe przetrwały ~ ~ 15 lat. Sądzę, że maszyny 64-bitowe wytrzymają znacznie dłużej. W przypadku większej liczby arytmetyka z wieloma dokładnościami będzie w porządku i wątpię, czy wydajność obliczania liczby cyfr będzie miała znaczenie.
Ira Baxter
74

Najprościej jest zrobić:

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

log10 jest zdefiniowany w <cmath>lub <math.h>. Musisz to profilować, aby sprawdzić, czy jest szybszy niż którykolwiek z innych opublikowanych tutaj. Nie jestem pewien, jak solidne jest to pod względem precyzji punktu zmiennoprzecinkowego. Ponadto argument jest bez znaku jako wartości ujemne, a log tak naprawdę się nie miesza.

Skizz
źródło
7
W przypadku 32-bitowych int i 56-bitowych liczb zmiennoprzecinkowych to prawdopodobnie działa. Jeśli dane wejściowe są długie (64 bity), 56 bitów logu podwójnej precyzji może spowodować, że dadzą błędną odpowiedź w przypadku wartości bliskich dużych wartości 10 ^ n. Spodziewaj się kłopotów powyżej 2 ^ 50.
Ira Baxter
1
Powstaje również pytanie, jak dokładne są funkcje dziennika. Nie sprawdziłem, jak dokładne są w nowoczesnych bibliotekach i nie czułbym się komfortowo, ślepo ufając, że są dobre dla jednej części na miliard.
David Thornley
@DavidThornley: log lub inne funkcje matematyczne są doskonale precyzyjne, chyba że określono je w wierszu poleceń kompilatora. niektóre zostaną przekonwertowane na elementy wewnętrzne x86 w czasie kompilacji. niektóre nie istnieją i rozwiną się w formuły istniejących elementów wewnętrznych. na przykład, jeśli używasz, -fpfastmożesz zobaczyć użycie narzędzi SSE zamiast x87, co daje mniej gwarancji na precyzję IIRC. ale domyślnie nie ma problemu.
v.oddou,
@DavidThornley: To więcej niż precyzja. Pytanie brzmi, czy jest zagwarantowane, czy nie, że log10 (10 ^ k) ≥ k dla wszystkich odpowiednich k. Oznacza to, że gwarantuje się, że każdy nieunikniony błąd zaokrągleń idzie we właściwym kierunku. k + eps w rezultacie działa, k - eps nie. A „Idealnie precyzyjne” jest naiwne.
gnasher729
1
Test i> 0 można zoptymalizować do i> 9
Pat
60

Być może źle zrozumiałem pytanie, ale czy to nie działa?

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)))))))));  
}  
Ćwiek
źródło
29
I nie zdziwiłbym się, gdyby to rozwiązanie było najszybsze.
VisioN
32
int digits = 0; while (number != 0) { number /= 10; digits++; }

Uwaga: „0” będzie miało 0 cyfr! Jeśli potrzebujesz, aby 0 wyglądało na 1 cyfrę, użyj:

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

(Dzięki Kevin Fegan)

Na koniec użyj programu profilującego, aby wiedzieć, która ze wszystkich odpowiedzi tutaj będzie szybsza na twoim komputerze ...

squelart
źródło
3
To może, ale nie musi, być szybsze niż podejście z rozwiniętą pętlą, które zastosowałem - musiałbyś profilować różnicę (na dłuższą metę powinno być nieistotne).
Vitali
Zgoda, profilowanie to jedyny sposób, aby naprawdę wiedzieć na pewno! Zaktualizowałem swoją odpowiedź tym komentarzem, ponieważ odpowiedź ceil (log10 ()) Bena S. zniknęła.
squelart
11

Żart: Jest najbardziej efektywny sposób (liczba cyfr jest obliczana w czasie kompilacji):

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

Może być przydatne do określenia szerokości wymaganej dla pola liczbowego w formatowaniu, elementach wejściowych itp.

blinnov.com
źródło
4
Po pierwsze, twoje rozwiązanie nie działa dla 0. Po drugie, twoje rozwiązanie nie ma zastosowania do ogólnego przypadku zmiennej. Po trzecie, jeśli używasz stałego literału, wiesz już, ile ma cyfr.
Vitali
Działa też dla 0. Działa również na każdej podstawie. Reszta to ważne punkty, które już przedstawiłem.
blinnov.com
3
Nie sądzę, żeby tak było. To kończy się 0niepowodzeniem w przypadku bazy 1:) i daje dzielenie przez zero, jeśli podstawa jest podana jako 0. Można to jednak naprawić. W każdym razie czepiam się bardzo starego postu, więc przepraszam, po prostu myślę, że to nie musi być żartem i może być przydatne.
tjm
9

Zobacz Hacks Bit Twiddling, aby zapoznać się z dużo krótszą wersją zaakceptowanej odpowiedzi. Ma to również tę zaletę, że można szybciej znaleźć odpowiedź, jeśli dane wejściowe mają rozkład normalny, sprawdzając najpierw duże stałe. (v >= 1000000000)łapie 76% wartości, więc sprawdzenie, czy pierwsze będzie średnio szybsze.

Josh Haberman
źródło
Nie jest jasne, czy kręcenie bitów jest rzeczywiście szybsze. Nawet w najgorszym przypadku moje zmodyfikowane podejście wymaga 4 porównań (może być w stanie sprowadzić je do 3, jeśli zbadam dalej partycjonowanie, chociaż wygląda to mało prawdopodobne). Poważnie wątpię, czy zostanie to pokonane przez operacje arytmetyczne + ładowanie pamięci (chociaż przy wystarczającym dostępie te znikają w pamięci podręcznej procesora). Pamiętaj, że w podanym przez nich przykładzie ukrywają również podstawę dziennika 2 jako abstrakcyjną funkcję IntegerLogBase2 (która sama w sobie nie jest tania).
Vitali
Podobnie jak w przypadku kontynuacji, tak, jeśli liczby są normalnie rozłożone, sprawdzenie kolejności jest szybsze. Jednak w najgorszym przypadku ma zdegenerowany przypadek, gdy jest dwukrotnie wolniejszy. Podejście podzielone na liczby cyfr zamiast przestrzeni wejściowej oznacza, że ​​zachowanie nie ma zdegenerowanego przypadku i zawsze działa optymalnie. Ponadto pamiętaj, że zakładasz, że liczby będą równomiernie rozłożone. W rzeczywistości bardziej prawdopodobne jest, że podążą za jakąś dystrybucją związaną z <a href=" en.wikipedia.org/wiki/…> - to moje przypuszczenie.
Vitali
Nieco kręcące się hacki nie są szybsze niż powyższa metoda partycjonowania, ale są potencjalnie interesujące, jeśli masz tutaj bardziej ogólny przypadek, taki jak float.
Corwin Joy
1
Bitowe hacki sugerują sposób na uzyskanie int log10, biorąc pod uwagę int log2. Sugeruje kilka sposobów uzyskania int log2, w większości obejmujących kilka porównań / gałęzi. (Myślę, że nie doceniasz kosztu nieprzewidywalnych gałęzi, Vitali). Jeśli możesz użyć inline x86 asm, instrukcja BSR poda wartość int log2 (tj. Indeks bitowy najbardziej znaczącego bitu zestawu). Jest trochę wolny na K8 (opóźnienie 10 cykli), ale szybki na Core 2 (opóźnienie 2 lub 3 cykle). Nawet na K8 może być szybszy niż porównania.
Peter Cordes,
Na K10 lzcnt liczy wiodące zera, więc jest prawie to samo, co bsr, ale wejście 0 nie jest już specjalnym przypadkiem z niezdefiniowanymi wynikami. Opóźnienia: BSR: 4, LZCNT: 2.
Peter Cordes
8

przekonwertować na ciąg, a następnie użyć funkcji wbudowanych

unsigned int i;
cout<< to_string(i).length()<<endl;
wugoat
źródło
7
int x = 1000;
int numberOfDigits = x ? static_cast<int>(log10(abs(x))) + 1 : 1;
bemaru
źródło
3
Chociaż jest to wydajne pod względem LOC, jak zauważono w przyjętej odpowiedzi, użycie dziennika prawdopodobnie nie zapewni najlepszej wydajności.
Ian,
@Ian Dlaczego nie? To tylko kilka instrukcji FPU. Mile lepiej niż wszystkie gałęzie i pętle w innych odpowiedziach.
Markiz Lorne
5

Poprzedni plakat sugerował pętlę dzielącą przez 10. Ponieważ mnożenia na nowoczesnych komputerach są dużo szybsze, poleciłbym zamiast tego następujący kod:

 int digits = 1, pten=10; while ( pten <= number ) { digits++; pten*=10; }
Ira Baxter
źródło
1
diabeł tkwi w szczegółach - co się dzieje z powiedzmy std :: numeric_limits <int> :: max == number - może mieć problem z zakończeniem
pgast
2
Jeśli martwisz się tym przypadkiem, możesz dodać jeden dodatkowy IF, aby obsłużyć bardzo duże wartości.
Ira Baxter
2
Powinienem zauważyć, że na maszynach x86, mnożenie przez stałą 10, tak jak w tym przypadku, może być faktycznie zaimplementowane przez kompilator jako LEA R2, [8 * R1 + R1], ADD R1, R2, więc zajmuje maksymalnie 2 zegary. Mnożenie przez zmienne zajmuje dziesiątki zegarów, a dzielenie jest znacznie gorsze.
Ira Baxter
Zaletą metody dzielenia jest to, że nie musisz martwić się liczbami ujemnymi.
Johannes Schaub - litb
1
Porównałem podejście oparte na multiplikacji (z fabułami w celu usunięcia problemu ze znakiem) w porównaniu z podejściem dzielenia. Na moim komputerze metoda dzielenia jest dwukrotnie wolniejsza niż metoda mnożenia. To, czy jest to przedwczesna optymalizacja, czy nie, zależy tak naprawdę od tego, gdzie i jak się to nazywa.
Spacemoose
5

Architektura ppc ma instrukcję zliczania bitów. Dzięki temu możesz określić podstawę logu 2 dodatniej liczby całkowitej w jednej instrukcji. Na przykład wersja 32-bitowa to:

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

Jeśli możesz obsłużyć mały margines błędu przy dużych wartościach, możesz przekonwertować to na dziennik o podstawie 10 za pomocą kilku kolejnych instrukcji:

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

Jest to specyficzne dla platformy i nieco niedokładne, ale również nie wymaga rozgałęzień, dzielenia ani konwersji na zmiennoprzecinkowe. Wszystko zależy od tego, czego potrzebujesz.

Znam tylko instrukcje ppc, ale inne architektury powinny mieć podobne instrukcje.


źródło
To rozwiązanie oblicza log2 (15) = 4 bity i log2 (9) = 4 bity. Ale 15 i 9 wymagają do wydrukowania innej liczby cyfr dziesiętnych. Więc to nie działa, chyba że nie przeszkadza ci drukowanie liczb ze zbyt dużą liczbą cyfr. Ale w takim przypadku zawsze możesz wybrać „10” jako odpowiedź na int.
Ira Baxter
Wow, przybliżona funkcja. Miły.
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;
 }

Jest to prawdopodobnie najprostszy sposób rozwiązania problemu, zakładając, że zależy Ci tylko na cyfrach przed przecinkiem i przyjmując, że cokolwiek mniej niż 10 to tylko 1 cyfra.

RoryHector
źródło
1

Podoba mi się odpowiedź Iry Baxtera. Oto wariant szablonu, który obsługuje różne rozmiary i radzi sobie z maksymalnymi wartościami całkowitymi (zaktualizowanymi w celu podniesienia górnej granicy wyewidencjonowania z pętli):

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

Aby faktycznie uzyskać lepszą wydajność z wyciągania dodatkowego testu z pętli, musisz wyspecjalizować max_decimal (), aby zwracać stałe dla każdego typu na twojej platformie. Wystarczająco magiczny kompilator mógłby zoptymalizować wywołanie max_decimal () do stałej, ale obecnie większość kompilatorów specjalizuje się lepiej. W obecnym kształcie ta wersja jest prawdopodobnie wolniejsza, ponieważ max_decimal kosztuje więcej niż testy usunięte z pętli.

Zostawię to wszystko jako ćwiczenie dla czytelnika.

janm
źródło
Chcesz, aby górny limit sprawdzał najpierw osobne warunkowe testy, więc nie sprawdzaj go przy każdej iteracji pętli.
Ira Baxter
Nie chcesz wstawiać 10 do tej temperatury. Kompilator może rozważyć pomnożenie przez t, aby pomnożyć przez zmienną rzeczywistą, i użyć instrukcji mnożenia ogólnego przeznaczenia. Jeśli zamiast tego napiszesz „wynik * = 10;” kompilator z pewnością zauważy mnożenie przez stałą 10 i zaimplementuje to z kilkoma zmianami i dodaniami, co jest niezwykle szybkie.
Ira Baxter
Gdyby mnożenie przez t było zawsze mnożeniem przez 10, to tak, kompilator mógłby dokonać redukcji siły. Jednak w tym przypadku t nie jest niezmienna w pętli (jest to tylko modyfikacja funkcji potęgowej liczby całkowitej, którą miałem w pobliżu). Prawidłowa optymalizacja to specjalizacja w typie zwracającym stałą. Jednak masz rację, że w tym przypadku funkcja zawsze podnosi 10 do potęgi, a nie dowolną liczbę całkowitą do potęgi, a zmniejszenie siły daje dobrą wygraną. Więc dokonałem zmiany… Tym razem dalsze zmiany są tak naprawdę pozostawione jako ćwiczenie! (Przepełnienie stosu to duży czas pochłaniania ...)
janm,
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
źródło
0

Kolejny fragment kodu, działający w zasadzie tak samo jak Vitali, ale wykorzystujący wyszukiwanie binarne. Tablica Powers jest inicjowana z opóźnieniem raz na wystąpienie typu bez znaku. Przeciążenie typu ze znakiem obsługuje znak minus.

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

Jeśli komuś zależy na dalszej optymalizacji, pamiętaj, że pierwszy element tablicy mocy nigdy nie jest używany, a lpojawia się +12 razy.

Alexey Biryukov
źródło
0

w przypadku, gdy potrzebna jest liczba cyfr ORAZ wartość każdej pozycji cyfry użyj tego:

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

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

digitpodaje wartość w pozycji numeru, która jest aktualnie przetwarzana w pętli. na przykład dla numeru 1776 wartość cyfry to:
6 w 1. pętli
7 w 2. pętli
7 w 3. pętli
1 w czwartej pętli

JFS
źródło
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
źródło
Korekta dla „Praktycznego żartu” z „blinnov.com” powyżej
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
źródło
0

dla liczby całkowitej `` X '' chcesz znać liczbę cyfr, w porządku bez użycia żadnej pętli, to rozwiązanie działa w jednej formule tylko w jednym wierszu, więc jest to najbardziej optymalne rozwiązanie tego problemu, jakie kiedykolwiek widziałem.

 int x = 1000 ; 
 cout<<numberOfDigits = 1+floor(log10(x))<<endl ; 
Sameh Adel
źródło
Zawodzi dla INT_MAX, a także dla liczb ujemnych.
ranu
W jaki sposób @ranu zawodzi w przypadku INT_MAX? Kiedy argument jest konwertowany na double? A może masz na myśli jakieś niemożliwe dane wejściowe w postaci liczb całkowitych z cyframi dziesiętnymi INT_MAX? Która z poniższych odpowiedzi również zawiodłaby?
Markiz Lorne
0
int numberOfDigits(int n){

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

Oto, co bym zrobił, jeśli chcesz to dla podstawy 10, jest dość szybki i prawdopodobnie nie dostaniesz stosu overflock kup licząc liczby całkowite

Mc Stevens
źródło
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
źródło
0

Jeśli szybsze jest bardziej wydajne, oznacza to poprawę w stosunku do poprawy Andrei Alexandrescu . Jego wersja była już szybsza niż naiwny sposób (dzielenie przez 10 przy każdej cyfrze). Poniższa wersja ma stały czas i jest szybsza przynajmniej na x86-64 i ARM dla wszystkich rozmiarów, ale zajmuje dwa razy więcej kodu binarnego, więc nie jest tak przyjazna dla pamięci podręcznej.

Benchmarki dla tej wersji w porównaniu z wersją alexandrescu na moim PR na Facebooku szaleństwo .

Działa dalej unsigned, nie 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
źródło
0

Pracowałem nad programem, który wymagał ode mnie sprawdzenia, czy użytkownik poprawnie odpowiedział, ile cyfr znajduje się w liczbie, więc musiałem opracować sposób sprawdzania liczby cyfr w liczbie całkowitej. Okazało się, że było to stosunkowo łatwe do rozwiązania.

double check=0, exponent=1000;

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

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

To była moja odpowiedź, która obecnie działa z liczbami mniejszymi niż 10 ^ 1000 cyfr (można to zmienić, zmieniając wartość wykładnika).

PS Wiem, że ta odpowiedź jest opóźniona o dziesięć lat, ale dotarłem tu w 2020 roku, więc inni mogą z niej skorzystać.

Daniel Bercero
źródło
-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);
    }
};

gdzie powers_and_maxmamy (10^n)-1dla wszystkich ntakie, że

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

i std::numeric_limits<type>::max()w tablicy:

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

oto prosty 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);

Oczywiście każda inna implementacja uporządkowanego zbioru może być użyta do powers_and_maxi jeśli byłaby wiedza, że ​​będzie klaster, ale brak wiedzy o tym, gdzie może być klaster, być może samodopasowująca się implementacja drzewa może być najlepsza

pgast
źródło
-1

efektywny sposób

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
źródło
-1

Aktualizacja preferowanego rozwiązania w C ++ 11:

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

zapobiega tworzeniu się szablonów za pomocą double, et. glin.

gerardw
źródło
-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
źródło
-2

Oto mój sposób na zrobienie tego:

   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
źródło
2
while true / break syndrome: D
Петър Петров
-1 to to samo podejście, które podała pierwsza odpowiedź sześć lat wcześniej i nic nie dodaje (w rzeczywistości jest znacznie gorsze).
-4

Oto inne podejście:

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

To może nie być wydajne, po prostu coś innego niż to, co sugerowali inni.

Ashwin
źródło
4
Prośba była bardzo wydajna. To jest odwrotnie.
Ira Baxter