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

Quel est un moyen 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. Devrait être plus rapide que l’approche beaucoup plus courte basée sur le logarithme. Si vous ne vous souciez pas de compter le «-», supprimez le + 1.

// generic solution template  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]; } 

La manière la plus simple est de faire:

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

log10 est défini dans ou . Vous devez définir ce profil pour voir s’il est plus rapide que les autres affichés ici. Je ne suis pas sûr de la robustesse de ce point en ce qui concerne la précision des points flottants. En outre, l’argument n’est pas signé en tant que valeurs négatives et le journal ne se mélange pas vraiment.

J’ai peut-être mal compris la question, mais est-ce que cela ne le fait 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++; } 

Note: “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)

Au final, utilisez un profileur pour savoir laquelle de toutes les réponses sera plus rapide sur votre machine …

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

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

Peut être utile pour déterminer la largeur requirejse 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 rapidement si votre entrée est normalement dissortingbuée, en vérifiant d’abord les grandes constantes. (v >= 1000000000) capte 76% des valeurs, donc vérifier que la première sera en moyenne plus rapide.

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

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

Une affiche précédente suggérait une boucle qui divise par 10. Comme 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 la base de journal 2 d’un entier positif dans une seule instruction. Par exemple, 32 bits serait:

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

Si vous pouvez gérer une faible marge d’erreur sur les grandes valeurs, vous pouvez la convertir en base de journalisation 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 twig, division ou conversion en virgule flottante. Tout dépend de ce dont vous avez besoin.

Je ne connais que les instructions ppc, mais les autres architectures doivent avoir des instructions similaires.

  #include  #include  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 "< 

C'est probablement la manière la plus simple de résoudre votre problème, en supposant que vous ne vous souciez que des chiffres avant la décimale et que vous présumiez que moins de 10 chiffres ne représentent qu'un chiffre.

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

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

 #include  template T max_decimal() { T t = 1; for (unsigned i = boost::integer_traits::digits10; i; --i) t *= 10; return t; } template unsigned digits(T v) { if (v < 0) v = -v; if (max_decimal() <= v) return boost::integer_traits::digits10 + 1; unsigned digits = 1; T boundary = 10; while (boundary <= v) { boundary *= 10; ++digits; } return digits; } 

Pour obtenir les meilleures performances en levant le test supplémentaire hors 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 à max_decimal () à une constante, mais la spécialisation est meilleure avec la plupart des compilateurs aujourd'hui. En l'état actuel, cette version est probablement plus lente car max_decimal coûte plus cher que les tests retirés de la boucle.

Je vais laisser tout cela comme exercice pour le lecteur.

 /// 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 ) ) ) ); } 
 template  class number_of_decimal_digits { const powers_and_max mPowersAndMax; public: number_of_decimal_digits(){ } inline size_t ndigits( type i) const { if(i<0){ i += (i == std::numeric_limits::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 ssortingng_ndigits(const type& i) const { return (i<0) + ndigits(i); } inline size_t operator[](const type& i) const { return string_ndigits(i); } }; 

où dans powers_and_max nous avons (10^n)-1 pour tout n tel que

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

et std::numeric_limits::max() dans un tableau:

 template  struct powers_and_max : protected std::vector{ typedef std::vector 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::max()))); int j = 0; type i = 10; for( ; j::max()); push_back(std::numeric_limits::max()); } }; 

voici un test simple:

 number_of_decimal_digits 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 pour powers_and_max et s'il y avait des connaissances sur le clustering, mais aucune connaissance de la position du cluster, une implémentation auto-ajustable de l'arbre serait peut-être la meilleure.

façon efficace

 int num; int count = 0; while(num) { num /= 10; ++count; } 

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

Encore un autre extrait de code, faisant essentiellement la même chose que Vitali, mais utilisant une recherche binary. Le tableau de puissances est initialisé par défaut une fois par instance de type non signé. La surcharge de type signé prend en charge le signe moins.

 #include  #include  #include  template  size_t NumberOfDecPositions ( T v, typename std::enable_if::value>::type* = 0 ) { typedef std::array::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  size_t NumberOfDecPositions ( T v, typename std::enable_if::value>::type* = 0 ) { typedef typename std::make_unsigned::type unsigned_type; if ( v < 0 ) return NumberOfDecPositions ( static_cast(-v) ) + 1; else return NumberOfDecPositions ( static_cast(v) ); } 

Si quelqu’un se soucie de l’optimisation supplémentaire, veuillez noter que le premier élément du tableau des puissances n’est jamais utilisé, et le l apparaît avec +1 2 fois.

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

 int64_t = number, digitValue, digits = 0; // or "int" for 32bit while (number != 0) { digitValue = number % 10; digits ++; number /= 10; } 

digit vous donne la valeur au numéro de poste actuellement traité dans la boucle. Par exemple, pour le numéro 1776, la valeur numérique 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

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

 #include  #include  template  typename std::enable_if::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 du 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; } 
 // Meta-program to calculate number of digits in (unsigned) 'N'. template  struct numberlength { // http://stackoverflow.com/questions/1489830/ enum { value = ( 1<=N && N::value ) }; }; template  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) ); 
 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. Il est assez rapide et vous n'obtiendrez pas de débordement de la stack.

 int x = 1000; int numberOfDigits = static_cast(log10(x)) + 1; 

pour l’entier ‘X’, vous voulez connaître le nombre de chiffres, sans utiliser de boucle, cette solution n’agit que dans une formule sur une seule ligne.

  int x = 1000 ; cout< 

C’est ma façon de le faire:

  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 les autres ont suggéré.