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

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

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

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.

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

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 ...

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.

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.

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

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

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

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

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.

 #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.

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.

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

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.

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

// Meta-program to calculate number of digits in (unsigned) 'N'.    
template <unsigned long long N, unsigned base=10>
struct numberlength
{   // http://stackoverflow.com/questions/1489830/
    enum { value = ( 1<=N && N<base ? 1 : 1+numberlength<N/base, base>::value ) };
};

template <unsigned base>
struct numberlength<0, base>
{
    enum { value = 1 };
};

{
    assert( (1 == numberlength<0,10>::value) );
}
assert( (1 == numberlength<1,10>::value) );
assert( (1 == numberlength<5,10>::value) );
assert( (1 == numberlength<9,10>::value) );

assert( (4 == numberlength<1000,10>::value) );
assert( (4 == numberlength<5000,10>::value) );
assert( (4 == numberlength<9999,10>::value) );

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

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 ; 

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

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

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

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.

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

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

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.

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

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

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.