modo efficace per determinare il numero di cifre di un numero intero
https://stackoverflow.com/questions/1489830
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Che cosa è un efficace modo di determinare quante cifre ci sono in un numero intero in C ++?
Soluzione
Bene, il modo più efficiente, presumendo che si conosce la dimensione del numero intero, sarebbe una ricerca. Dovrebbe essere più veloce rispetto al metodo logaritmo in base molto più breve. Se non si cura di contare il '-'., Togliere il + 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];
}
Altri suggerimenti
Il modo più semplice è quello di fare:
unsigned GetNumberOfDigits (unsigned i)
{
return i > 0 ? (int) log10 ((double) i) + 1 : 1;
}
log10 è definita in <cmath> o <math.h>. Avresti bisogno al profilo questo per vedere se è più veloce di tutti gli altri qui pubblicato. Io non sono sicuro di come questo è robusto per quanto riguarda galleggiare punto precisione. Inoltre, l'argomento non è firmato come valori negativi e log in realtà non mescolare.
Forse ho capito male la domanda, ma non questo fatto?
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++; }
Nota: "0" avrà 0 cifre! Se avete bisogno di 0 a 1 sembrano avere cifra, utilizzare:
int digits = 0; do { number /= 10; digits++; } while (number != 0);
(Grazie Kevin Fegan)
Alla fine, utilizzare un profiler di sapere quale di tutte le risposte qui sarà più veloce sulla vostra macchina ...
scherzo: Si tratta di il modo più efficiente (numero di cifre viene calcolato al momento della compilazione):
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 };
};
Può essere utile per determinare la larghezza richiesta per il campo numero di formattazione, elementi di input etc.
Bit girarsi Hacks per una versione molto più breve della risposta che accettato. Essa ha anche il vantaggio di trovare la risposta più presto se l'input è distribuito normalmente, controllando le grandi costanti di prima. (v >= 1000000000) cattura 76% dei valori, in modo da verificare che la prima volontà, in media, essere più veloce.
convertire in stringa e quindi utilizzare le funzioni built-in
unsigned int i;
cout<< to_string(i).length()<<endl;
Un poster precedente ha suggerito un ciclo che divide per 10. Dal momento che si moltiplica sulle macchine moderne sono molto più veloce, mi consiglia il seguente codice invece:
int digits = 1, pten=10; while ( pten <= number ) { digits++; pten*=10; }
L'architettura ppc ha un'istruzione di conteggio bit. Con questo, è possibile determinare il logaritmo in base 2 di un numero intero positivo in una singola istruzione. Ad esempio, a 32 bit potrebbe essere:
#define log_2_32_ppc(x) (31-__cntlzw(x))
Se si riesce a gestire un piccolo margine di errore sui valori di grandi dimensioni è possibile convertire che al logaritmo in base 10 con un altro paio di istruzioni:
#define log_10_estimate_32_ppc(x) (9-(((__cntlzw(x)*1233)+1545)>>12))
Questo è specifica piattaforma e leggermente imprecisa, ma anche non comporta rami, scissione o conversione in virgola mobile. Tutto dipende da quello che ti serve.
Ho solo conoscere le istruzioni ppc fuori mano, ma altre architetture dovrei avere istruzioni simili.
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;
}
Questo è probabilmente il modo più semplice di risolvere il tuo problema, supponendo che vi interessa soltanto cifre prima del decimale e assumendo niente di meno che 10 è solo 1 cifra.
#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
)
)
);
}
Mi piace la risposta di Ira Baxter. Qui è una variante del modello che gestisce le varie dimensioni e si occupa con i valori massimi interi (aggiornato per issare il controllo limite superiore fuori dal giro):
#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;
}
Per realmente ottenere il miglioramento delle prestazioni dal sollevamento la prova supplementare fuori dal giro, è necessario specializzarsi max_decimal () per restituire le costanti per ogni tipo sulla vostra piattaforma. Un compilatore sufficientemente magia potrebbe ottimizzare la chiamata a max_decimal () per una costante, ma la specializzazione è meglio con la maggior parte dei compilatori di oggi. Così com'è, questa versione è probabilmente più lento a causa max_decimal costa più dei test rimossi dal ciclo.
Lascio tutto ciò come un esercizio per il lettore.
/// 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);
}
};
dove nel powers_and_max abbiamo (10^n)-1 per tutti n tali che
(10^n) < std::numeric_limits<type>::max()
e std::numeric_limits<type>::max() in un array:
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());
}
};
Ecco un semplice 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);
Naturalmente ogni altra realizzazione di un insieme ordinato potrebbe essere utilizzato per powers_and_max e se c'era la conoscenza che non ci sarebbe il clustering, ma nessuna conoscenza di dove il gruppo potrebbe essere forse un auto regolazione implementazione albero potrebbe essere migliore
modo 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;
}
Ancora un altro frammento di codice, facendo fondamentalmente lo stesso come Vitali, ma si avvale di ricerca binaria. Poteri array è inizializzato pigrizia volta per esempio tipo senza segno. sovraccarico di tipo Firmato si prende cura del segno meno.
#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) );
}
Se qualcuno si prende cura di un'ulteriore ottimizzazione, si ricorda che il primo elemento di poteri matrice viene mai usato, e la l appare con +1 2 volte.
se il numero di cifre E il valore di ciascuna posizione di cifra è necessario usare questo:
int64_t = number, digitValue, digits = 0; // or "int" for 32bit
while (number != 0) {
digitValue = number % 10;
digits ++;
number /= 10;
}
digit ti dà il valore alla postition numero che è attualmente processato nel ciclo. ad esempio, il numero 1776 il valore della cifra è:
6 nel 1 ° ciclo
7 nel 2 ° ciclo
7 nel 3 ° ciclo
1 nel 4 ° ciclo
C ++ 11 aggiornamento soluzione preferita:
#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;
}
impedisce modello di istanza con il doppio, 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);
}
Questo è quello che vorrei fare, se lo vuoi per 10.Its di base piuttosto veloce e si prolly non otterrete una pila overflock acquistare interi conteggio
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";
Se più veloce è più efficiente, questo è un miglioramento su Andrei Alexandrescu di miglioramento . La sua versione era già più veloce del modo ingenuo (dividendo per 10 ad ogni cifra). La versione che segue è un tempo costante e veloce almeno su x86-64 e ARM per tutte le dimensioni, ma occupa il doppio di codice binario, quindi non è come la cache-friendly.
parametri di riferimento per questa versione vs la versione di Alexandrescu sulla mia PR su facebook follia .
Funziona su 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);
}
per intero 'X' che si desidera conoscere il numero di cifre, va bene senza l'utilizzo di alcun ciclo, questa soluzione agire in una formula in una linea unica quindi questa è la soluzione più ottimale che abbia mai visto a questo problema.
int x = 1000 ;
cout<<numberOfDigits = 1+floor(log10(x))<<endl ;
Questo è il mio modo per farlo:
int digitcount(int n)
{
int count = 1;
int temp = n;
while (true)
{
temp /= 10;
if (temp != 0) ++count;
if (temp == 0) break;
}
return count;
}
Ecco un approccio diverso:
digits = sprintf(numArr, "%d", num); // where numArr is a char array
if (num < 0)
digits--;
Questo potrebbe non essere efficace, solo qualcosa di diverso da quello che gli altri hanno suggerito.
