moyen efficace de déterminer le nombre de chiffres en un nombre entier
https://stackoverflow.com/questions/1489830
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Qu'est-ce qu'un très efficace moyen de déterminer le nombre de chiffres, il y a dans un nombre entier en C ++?
La solution
Eh bien, la façon la plus efficace, en supposant que vous connaissez la taille de l'entier, serait une recherche. Devrait être plus rapide que l'approche basée sur logarithme beaucoup plus courte. Si vous ne se soucient pas de compter le « - »., Retirez 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];
}
Autres conseils
La façon la plus simple est de le faire:
unsigned GetNumberOfDigits (unsigned i)
{
return i > 0 ? (int) log10 ((double) i) + 1 : 1;
}
log10 est défini dans <cmath> ou <math.h>. Vous aurez besoin de ce profil pour voir si elle est plus rapide que tous les autres affichés ici. Je ne suis pas sûr de la solidité de c'est en ce qui concerne la précision float point. En outre, l'argument est non signé en tant que valeurs négatives et le journal ne se mélangent pas vraiment.
Peut-être que j'ai mal compris la question, mais ne pas le faire?
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 0 à semblent avoir 1 chiffre, utilisez:
int digits = 0; do { number /= 10; digits++; } while (number != 0);
(Merci Kevin Fegan)
En fin de compte, utilisez un profileur de savoir qui, de toutes les réponses ici sera plus rapide sur votre machine ...
blague: Ceci est la moyen le plus efficace (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 la mise en forme, des éléments d'entrée etc.
Voir Bit bidouilles Hacks pour une version beaucoup plus courte de la réponse que vous accepté. Il a également l'avantage de trouver la réponse plus tôt si votre entrée est normalement distribué, en vérifiant les grandes constantes d'abord. (v >= 1000000000) attire 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()<<endl;
Une affiche précédente suggère une boucle qui divise par 10. Depuis multiplications sur des machines modernes sont beaucoup plus rapides, je vous recommande 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 log 2 d'un nombre 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 les grandes valeurs que vous pouvez convertir en log base 10 avec encore quelques instructions:
#define log_10_estimate_32_ppc(x) (9-(((__cntlzw(x)*1233)+1545)>>12))
Ceci est la plate-forme spécifique et un peu imprécis, mais implique aussi pas de branches, la division ou la conversion en virgule flottante. Tout dépend de ce dont vous avez besoin.
Je ne connais que les instructions ppc hors main, mais d'autres architectures devrait avoir des instructions similaires.
int x = 1000;
int numberOfDigits = x ? static_cast<int>(log10(abs(x))) + 1 : 1;
#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;
}
Ceci est probablement la façon la plus simple de résoudre votre problème, en supposant que ne vous préoccupez chiffres avant la virgule et en supposant quoi que ce soit moins de 10 est à seulement 1 chiffre.
#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 adolfo.dimare@gmail.com
/// - \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 de 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 hisser le contrôle 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 obtenir effectivement l'amélioration des performances de levage test supplémentaire hors de la boucle, vous avez besoin de se spécialiser max_decimal () pour retourner 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 mieux avec la plupart des compilateurs aujourd'hui. En l'état actuel, cette version est probablement plus lente, car les coûts max_decimal plus que les tests retirés de la boucle.
Je vais laisser tout cela comme un exercice pour le lecteur.
/// Determine the number of digits for a 64 bit integer.
/// - Uses at most 5 comparisons.
/// - (cX) 2014 adolfo.dimare@gmail.com
/// - \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 <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_max nous avons (10^n)-1 pour tous n tels 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 mise en œuvre d'un ensemble ordonné peut être utilisé pour powers_and_max et s'il y avait des connaissances qu'il y aurait le regroupement, mais aucune connaissance de l'endroit où le groupe pourrait être peut-être un autoréglable la mise en œuvre de l'arbre pourrait être le meilleur
moyen 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;
}
Encore un autre extrait de code, en faisant essentiellement la même chose que de Vitali, mais utilise une recherche binaire. tableau puissances est paresseux initialisé une fois par instance de type non signé. 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 prend soin d'une optimisation plus poussée, s'il vous plaît noter que le premier élément du tableau de pouvoirs 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 chiffres est l'utilisation nécessaire 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 à la postition du nombre qui est en cours de traitement 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 boucle 4
11 C ++ mise à jour de 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;
}
// 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) );
int numberOfDigits(int n){
if(n<=9){
return 1;
}
return 1 + numberOfDigits(n/10);
}
est ce que je ferais, si vous le voulez pour 10.Its de base assez rapide et vous obtenez une pile prolly habitude overflock acheter des entiers comptant
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 amélioration de andrei Alexandrescu . Sa version était déjà plus rapide que la façon naïve (en divisant par 10 à chaque chiffre). La version ci-dessous est constante de temps et plus rapide au moins sur x86-64 et ARM pour toutes les tailles, mais occupe deux fois plus de code binaire, il est donc pas décrit comme cache.
Repères pour cette version vs la version Alexandrescu sur mon PR sur facebook folie .
Travaux sur unsigned, pas 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);
}
pour entier « X » vous voulez connaître le nombre de chiffres, d'accord sans utiliser la boucle, cet acte de solution dans une formule en une seule ligne c'est donc la solution la plus optimale que j'ai jamais vu à ce problème.
int x = 1000 ;
cout<<numberOfDigits = 1+floor(log10(x))<<endl ;
Ceci 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 autre approche:
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 ont suggéré.
