Moyen efficace de déterminer le nombre de chiffres dans un entier

145

Quelle est une manière très efficace de déterminer combien de chiffres il y a dans un entier en C ++?

Seth
la source
11
Dans quelle base? 2? dix?
Jacob Krall
2
Je voudrais le faire en base 10
Seth
1
Une fois, j'ai posé une question connexe: comment pouvez-vous obtenir le premier chiffre d'un int? Bon nombre des mêmes méthodologies que ci-dessous ont été utilisées dans les réponses des gens. Voici le lien au cas où il serait pertinent pour votre tâche [ stackoverflow.com/questions/701322/]
Dinah
L'assemblage en ligne est-il admissible?
György Andrasek le
1
Bien que toutes ces réponses soient en termes de base 10, il est assez facile de changer pour calculer le résultat pour n'importe quelle base souhaitée.
Ira Baxter

Réponses:

106

Eh bien, le moyen le plus efficace, en supposant que vous connaissez la taille de l'entier, serait une recherche. Doit être plus rapide que l'approche basée sur le logarithme beaucoup plus courte. Si vous ne vous souciez pas de compter les '-', supprimez le + 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
la source
5
Probablement plus rapide que ma réponse, bravo. Pour plus d'efficacité, si vous savez que vos nombres d'entrée seront pour la plupart petits (je suppose moins de 100 000), inversez les tests: si (x <10) renvoie 1; si (x <100) renvoie 2; etc., afin que la fonction fasse moins de tests et se termine plus rapidement.
squelart
29
Ou peut-être réorganiser et imbriquer les instructions if, pour faire une recherche binaire au lieu d'une recherche linéaire.
dave4420
1
Ce n'est pas une bonne idée. Que se passe-t-il lorsque l'architecture passe à des entiers de 256 bits? Vous devez vous rappeler de revenir et de modifier ce code. Dans la vraie vie, cela n'arrivera pas et cela va probablement être utilisé pour construire un tampon de la taille correcte, vous vous ouvrez maintenant à toutes sortes de problèmes de tampon sur des architectres plus grands.
Martin York
3
en supposant une distribution uniforme des nombres, la recherche linéaire inverse (à partir du nombre maximum de chiffres à 1) peut être plus rapide en moyenne que la recherche binaire car il y a beaucoup plus de nombres avec N chiffres qu'avec N-1 chiffres graphics.stanford.edu/~ seander /…
fa.
6
Je ne m'inquiéterais pas très fort des nombres entiers de 256 ou 128 bits. À moins que vous n'ayez besoin de compter le nombre d'électrons dans l'Univers (10 ^ 78 la dernière fois que je l'ai fait), 64 bits feront très bien l'affaire. Les machines 32 bits ont duré environ 15 ans. Je suppose que les machines 64 bits dureront beaucoup plus longtemps. Pour un plus grand nombre, l'arithmétique multiprécision conviendra, et je doute que l'efficacité du calcul du nombre de chiffres soit importante.
Ira Baxter le
74

Le moyen le plus simple est de faire:

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

log10 est défini dans <cmath>ou <math.h>. Vous auriez besoin de profiler ceci pour voir si c'est plus rapide que n'importe lequel des autres postés ici. Je ne sais pas à quel point cela est robuste en ce qui concerne la précision du point flottant. De plus, l'argument n'est pas signé car les valeurs négatives et le journal ne se mélangent pas vraiment.

Skizz
la source
7
Pour les entiers 32 bits et les flottants 56 bits, cela fonctionne probablement. Si l'entrée est longue (64 bits), les 56 bits du journal à double précision peuvent provoquer une mauvaise réponse dans le cas de valeurs proches de grandes valeurs de 10 ^ n. Attendez-vous à des problèmes au-dessus de 2 ^ 50.
Ira Baxter le
1
Il y a aussi la question de la précision des fonctions de journal. Je n'ai pas vérifié leur exactitude dans les bibliothèques modernes, et je ne serais pas à l'aise de croire aveuglément qu'elles sont bonnes à une partie sur un milliard.
David Thornley
@DavidThornley: le journal ou d'autres fonctions mathématiques sont parfaitement précis sauf indication contraire sur la ligne de commande du compilateur. certains seront convertis en intrinsèques x86 au moment de la compilation. certains n'existent pas et se développeront dans des formules d'intrinsèques existants. par exemple, si -fpfastvous utilisez, vous pourriez voir l'utilisation d'instrinsics SSE plutôt que x87, ce qui donne moins de garantie sur la précision IIRC. mais par défaut pas de problème.
v.oddou
@DavidThornley: C'est plus que de la précision. La question est de savoir s'il est garanti ou non que log10 (10 ^ k) ≥ k pour tous les k pertinents. C'est-à-dire que toute erreur d'arrondi inévitable aille dans la bonne direction. k + eps en conséquence fonctionne, k - eps ne le fait pas. Et «parfaitement précis» est naïf.
gnasher729
1
Le test i> 0 pourrait être optimisé à i> 9
Pat
60

Peut-être ai-je mal compris la question, mais cela ne suffit-il pas?

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
la source
29
Et je ne serais pas surpris que cette solution soit la plus rapide.
VisioN
32
int digits = 0; while (number != 0) { number /= 10; digits++; }

Remarque: "0" aura 0 chiffres! Si vous avez besoin de 0 pour avoir 1 chiffre, utilisez:

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

(Merci Kevin Fegan)

En fin de compte, utilisez un profileur pour savoir laquelle de toutes les réponses ici sera la plus rapide sur votre machine ...

squelart
la source
3
Cela peut ou non être plus rapide que l'approche de la boucle déroulée que j'ai adoptée - vous devrez profiler la différence (devrait être négligeable à long terme).
Vitali
D'accord, le profilage est le seul moyen d'en être vraiment sûr! J'ai mis à jour ma réponse avec ce commentaire, car la réponse ceil (log10 ()) de Ben S a disparu.
squelart
11

Blague pratique: c'est le moyen plus efficace (le nombre de chiffres est calculé à la compilation):

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

Peut être utile pour déterminer la largeur requise pour le champ numérique dans le formatage, les éléments d'entrée, etc.

blinnov.com
la source
4
Premièrement, votre solution ne fonctionne pas pour 0. Deuxièmement, votre solution est inapplicable au cas général d'une variable. Troisièmement, si vous utilisez un littéral constant, vous savez déjà combien de chiffres il contient.
Vitali le
Cela fonctionne aussi pour 0. Cela fonctionne également pour n'importe quelle base. Le reste sont des points valables que j'ai déjà exposés.
blinnov.com le
3
Je ne pense pas que ce soit le cas. Il échoue 0et échoue également sur la base 1:) et donne une division par zéro erreur si la base est donnée comme 0. Cela peut être corrigé. Quoi qu'il en soit, je suis en train de bousculer un très vieux post, alors désolé, c'est juste que je pense que cela n'a pas besoin d'être une blague et pourrait en fait être utile.
tjm
9

Voir Bit Twiddling Hacks pour une version beaucoup plus courte de la réponse que vous avez acceptée. Il a également l'avantage de trouver la réponse plus tôt si votre entrée est normalement distribuée, en vérifiant d'abord les grandes constantes. (v >= 1000000000)attrape 76% des valeurs, donc vérifier que le premier sera en moyenne plus rapide.

Josh Haberman
la source
On ne sait pas si le twiddling est réellement plus rapide. Même dans le pire des cas, mon approche modifiée nécessite 4 comparaisons (pourrait être en mesure de la ramener à 3 si j'examinais plus en détail le partitionnement, bien que cela semble peu probable). Je doute sérieusement que cela soit battu par des opérations arithmétiques + des charges de mémoire (bien que si on y accède suffisamment, celles-ci disparaissent dans le cache du processeur). Rappelez-vous, dans l'exemple qu'ils donnent, ils cachent également la base de journal 2 comme une fonction abstraite IntegerLogBase2 (qui elle-même n'est pas bon marché).
Vitali
Juste comme suivi, oui si les numéros sont normalement distribués, faire le contrôle dans l'ordre est plus rapide. Cependant, il a le cas dégénéré d'être deux fois plus lent dans le pire des cas. L'approche partitionnée par nombre de chiffres au lieu d'espace d'entrée signifie que le comportement n'a pas de cas dégénéré et fonctionne toujours de manière optimale. De plus, rappelez-vous que vous faites l'hypothèse que les nombres seront uniformément distribués. En fait, ils sont plus susceptibles de suivre une distribution liée à <a href=" en.wikipedia.org/wiki/…> , je suppose.
Vitali
Les hacks de twiddling ne sont pas plus rapides que la méthode de partition ci-dessus, mais ils sont potentiellement intéressants si vous aviez un cas plus général comme un flotteur ici.
Corwin Joy
1
Le bit twiddling hacks suggère un moyen d'obtenir le int log10, étant donné le int log2. Il suggère plusieurs façons d'obtenir int log2, impliquant principalement quelques comparaisons / branches. (Je pense que vous sous-estimez le coût des branches imprévisibles, Vitali). Si vous pouvez utiliser inline x86 asm, l'instruction BSR vous donnera le journal int2 d'une valeur (c'est-à-dire l'indice de bit d'un bit défini le plus significatif). C'est un peu lent sur K8 (latence de 10 cycles), mais rapide sur Core 2 (latence de 2 ou 3 cycles). Même sur K8, peut-être bien plus rapide que les comparaisons.
Peter Cordes
Sur K10, lzcnt compte les zéros non significatifs, donc c'est presque la même chose que bsr, mais une entrée de 0 n'est plus un cas particulier avec des résultats non définis. Latences: BSR: 4, LZCNT: 2.
Peter Cordes
8

convertir en chaîne puis utiliser les fonctions intégrées

unsigned int i;
cout<< to_string(i).length()<<endl;
wugoat
la source
7
int x = 1000;
int numberOfDigits = x ? static_cast<int>(log10(abs(x))) + 1 : 1;
bemaru
la source
3
Bien que cela soit efficace en termes de LOC, comme indiqué dans la réponse acceptée, l'utilisation du journal ne donnera probablement pas les meilleures performances.
Ian
@Ian Pourquoi pas? Ce ne sont que quelques instructions FPU. Miles mieux que toutes les branches et boucles dans d'autres réponses.
Marquis of Lorne
5

Une affiche précédente suggérait une boucle qui divise par 10. Étant donné que les multiplications sur les machines modernes sont beaucoup plus rapides, je recommanderais plutôt le code suivant:

 int digits = 1, pten=10; while ( pten <= number ) { digits++; pten*=10; }
Ira Baxter
la source
1
le diable est dans les détails - que se passe-t-il avec, disons std :: numeric_limits <int> :: max == number - il pourrait avoir un problème pour terminer
pgast
2
Si ce cas vous inquiète, vous pouvez ajouter un IF supplémentaire pour gérer de très grandes valeurs.
Ira Baxter le
2
Je dois observer que sur les machines x86, une multiplication par une constante 10 telle qu'utilisée dans ce cas peut en fait être implémentée par le compilateur comme LEA R2, [8 * R1 + R1], ADD R1, R2 donc il faut 2 horloges max. Les multiplications par variables prennent des dizaines d'horloges et les divisions sont bien pires.
Ira Baxter le
L'avantage de l'approche de division est que vous n'avez pas à vous soucier des nombres négatifs.
Johannes Schaub - litb
1
J'ai comparé l'approche de multipication (avec un fabs pour supprimer le problème de signe) par rapport à l'approche de division. Sur ma machine, l'approche de division est un facteur 2 plus lente que l'approche de multiplication. Que ce soit une optimisation prématurée ou non dépend vraiment de l'endroit et de la façon dont cela est appelé.
Spacemoose
5

L'architecture ppc a une instruction de comptage de bits. Avec cela, vous pouvez déterminer le journal de base 2 d'un entier positif en une seule instruction. Par exemple, 32 bits serait:

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

Si vous pouvez gérer une petite marge d'erreur sur de grandes valeurs, vous pouvez la convertir en journal de base 10 avec quelques instructions supplémentaires:

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

Ceci est spécifique à la plate-forme et légèrement imprécis, mais n'implique également aucune branche, division ou conversion en virgule flottante. Tout dépend de ce dont vous avez besoin.

Je ne connais que les instructions ppc de loin, mais d'autres architectures devraient avoir des instructions similaires.


la source
Cette solution calcule log2 (15) = 4 bits et log2 (9) = 4 bits. Mais 15 et 9 nécessitent des nombres de chiffres décimaux différents pour être imprimés. Cela ne fonctionne donc pas, à moins que cela ne vous dérange pas que vos chiffres soient parfois imprimés avec trop de chiffres. Mais dans ce cas, vous pouvez toujours choisir "10" comme réponse pour int.
Ira Baxter le
Wow, une fonction approximative. Agréable.
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;
 }

C'est probablement le moyen le plus simple de résoudre votre problème, en supposant que vous ne vous souciez que des chiffres avant la virgule et en supposant que tout ce qui est inférieur à 10 est juste 1 chiffre.

RoryHector
la source
1

J'aime la réponse d'Ira Baxter. Voici une variante de modèle qui gère les différentes tailles et traite les valeurs entières maximales (mise à jour pour extraire la limite supérieure de la boucle):

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

Pour réellement améliorer les performances en sortant le test supplémentaire de la boucle, vous devez spécialiser max_decimal () pour renvoyer des constantes pour chaque type sur votre plate-forme. Un compilateur suffisamment magique pourrait optimiser l'appel de max_decimal () à une constante, mais la spécialisation est meilleure avec la plupart des compilateurs aujourd'hui. Dans l'état actuel des choses, cette version est probablement plus lente car max_decimal coûte plus cher que les tests supprimés de la boucle.

Je laisse tout cela comme un exercice pour le lecteur.

janm
la source
Vous voulez que la limite supérieure vérifie d'abord une condition conditionnelle séparée afin de ne pas la vérifier à chaque itération de boucle.
Ira Baxter le
Vous ne voulez pas mettre 10 dans cette temp t. Le compilateur peut considérer la multiplication par t comme une multiplication par une variable réelle et utiliser une instruction de multiplication à usage général. Si vous avez plutôt écrit "result * = 10;" le compilateur remarquera sûrement la multiplication par la constante 10 et l'implémentera avec quelques changements et ajouts, ce qui est extrêmement rapide.
Ira Baxter
Si la multiplication par t était toujours une multiplication par 10, alors oui, le compilateur pourrait faire une réduction de force. Cependant, t n'est pas invariant en boucle dans ce cas (c'est juste une modification d'une fonction de puissance entière que j'avais traînée). L'optimisation correcte est la spécialisation sur le type retournant une constante. Cependant, vous avez raison de dire que, dans ce cas, la fonction élève toujours 10 à une puissance, et non un entier arbitraire à une puissance, et la réduction de force donne une bonne victoire. J'ai donc fait un changement ... Cette fois, d'autres changements sont vraiment laissés comme exercice! (Stack Overflow est un gros temps
perdu
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
la source
0

Encore un autre extrait de code, faisant fondamentalement la même chose que Vitali mais utilise la recherche binaire. Le tableau Powers est initialisé paresseusement une fois par instance de type non signé. La surcharge de type signé prend en charge le signe moins.

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

Si quelqu'un souhaite une optimisation supplémentaire, veuillez noter que le premier élément du tableau de puissances n'est jamais utilisé et lapparaît +12 fois.

Alexey Biryukov
la source
0

dans le cas où le nombre de chiffres ET la valeur de chaque position de chiffre sont nécessaires, utilisez ceci:

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

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

digitvous donne la valeur à la position numérique qui est actuellement traitée dans la boucle. par exemple pour le nombre 1776 la valeur du chiffre est:
6 dans la 1ère boucle
7 dans la 2ème boucle
7 dans la 3ème boucle
1 dans la 4ème boucle

JFS
la source
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
la source
Correction pour "Blague pratique" de 'blinnov.com' ci
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
la source
0

pour l'entier 'X', vous voulez connaître le nombre de chiffres, d'accord sans utiliser de boucle, cette solution agit dans une formule sur une seule ligne, c'est donc la solution la plus optimale que j'ai jamais vue à ce problème.

 int x = 1000 ; 
 cout<<numberOfDigits = 1+floor(log10(x))<<endl ; 
Sameh Adel
la source
Échec pour INT_MAX et aussi pour les nombres négatifs.
ranu
@ranu échoue pour INT_MAX comment? Quand l'argument est converti en double? Ou faites-vous référence à une entrée entière impossible avec des chiffres décimaux INT_MAX? Ce qui échouerait également toutes les autres réponses ici?
Marquis de Lorne
0
int numberOfDigits(int n){

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

C'est ce que je ferais, si vous le voulez pour la base 10, c'est assez rapide et vous n'obtiendrez probablement pas un overflock de pile en comptant des entiers

Mc Stevens
la source
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
la source
0

Si plus rapide est plus efficace, c'est une amélioration par rapport à l'amélioration d' Andrei alexandrescu . Sa version était déjà plus rapide que la manière naïve (en divisant par 10 à chaque chiffre). La version ci-dessous est à temps constant et plus rapide au moins sur x86-64 et ARM pour toutes les tailles, mais occupe deux fois plus de code binaire, elle n'est donc pas aussi conviviale pour le cache.

Benchmarks pour cette version vs la version d'Alexandrescu sur mon PR sur facebook Folly .

Fonctionne unsigned, non 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
la source
0

Je travaillais sur un programme qui me demandait de vérifier si l'utilisateur répondait correctement au nombre de chiffres dans un nombre, j'ai donc dû développer un moyen de vérifier le nombre de chiffres dans un entier. Cela a fini par être une chose relativement facile à résoudre.

double check=0, exponent=1000;

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

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

Cela a fini par être ma réponse qui fonctionne actuellement avec des nombres avec moins de 10 ^ 1000 chiffres (peut être changé en changeant la valeur de l'exposant).

PS Je sais que cette réponse a dix ans de retard, mais je suis arrivé ici en 2020 pour que d'autres personnes puissent l'utiliser.

Daniel Bercero
la source
-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);
    }
};

où en powers_and_maxnous avons (10^n)-1pour tout nce que

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

et std::numeric_limits<type>::max()dans un tableau:

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

voici un test simple:

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

Bien sûr, toute autre implémentation d'un ensemble ordonné pourrait être utilisée powers_and_maxet s'il y avait connaissance qu'il y aurait un clustering mais aucune connaissance de l'endroit où le cluster pourrait être peut-être une implémentation d'arbre auto-ajustable pourrait être la meilleure

pgast
la source
-1

façon efficace

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
la source
-1

Mise à jour C ++ 11 de la solution préférée:

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

empêche l'instanciation de modèle avec double, et. Al.

Gérardw
la source
-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
la source
-2

C'est ma façon de faire ça:

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

        return count;
    }
Léonard Urbano
la source
2
while true / break syndrome: D
Петър Петров
-1 c'est la même approche que la première réponse donnée six ans plus tôt, et elle n'ajoute rien (en fait c'est bien pire).
-4

Voici une approche différente:

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

Cela peut ne pas être efficace, juste quelque chose de différent de ce que d'autres suggèrent.

Ashwin
la source
4
La demande était extrêmement efficace. C'est le contraire.
Ira Baxter