manera eficiente de determinar el número de dígitos de un número entero
https://stackoverflow.com/questions/1489830
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Qué es un forma eficaz de determinar cuántos dígitos hay en un número entero en C ++?
Solución
Bueno, la forma más eficiente, suponiendo que se conoce el tamaño del entero, sería una búsqueda. En caso de ser más rápido que el enfoque basado en el logaritmo mucho más corto. Si no se preocupan por contar el '-'., Retire el + 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];
}
Otros consejos
La forma más sencilla de hacerlo es:
unsigned GetNumberOfDigits (unsigned i)
{
return i > 0 ? (int) log10 ((double) i) + 1 : 1;
}
log10 se define en <cmath> o <math.h>. Que había necesidad de Profile para ver si es más rápido que cualquiera de los otros publicados aquí. No estoy seguro de cómo esto es robusto con respecto a flotar precisión de punto. Además, el argumento no está firmado como valores negativos y conectarse realmente no mezclar.
Tal vez no he entendido bien la pregunta, pero no hago esto?
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" tendrá 0 dígitos! Si necesita someterse a 0 parecen tener 1 dígito, utilice:
int digits = 0; do { number /= 10; digits++; } while (number != 0);
(Gracias Kevin Fegan)
Al final, utilizar un generador de perfiles para saber cuál de todas las respuestas aquí será más rápido en su máquina ...
broma práctica: Este es la forma más eficiente (número de dígitos se calcula en tiempo de compilación):
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 };
};
Puede ser útil para determinar la anchura requerida para el campo de número en el formato, elementos de entrada etc.
Bit haciendo girar Hacks para una versión mucho más corta de la respuesta que aceptado. También tiene la ventaja de encontrar la respuesta antes si su entrada se distribuye normalmente, mediante la comprobación de las grandes constantes en primer lugar. (v >= 1000000000) capta el 76% de los valores, por lo que la comprobación de que la primera será en promedio más rápido.
convertir a cadena y luego utilizar las funciones incorporadas
unsigned int i;
cout<< to_string(i).length()<<endl;
Un usuario anterior sugirió un bucle que divide por 10. Dado que se multiplica en las máquinas modernas son mucho más rápido, te recomiendo el siguiente código en su lugar:
int digits = 1, pten=10; while ( pten <= number ) { digits++; pten*=10; }
La arquitectura PPC tiene una instrucción de conteo de bits. Con esto, se puede determinar el logaritmo en base 2 de un entero positivo en una sola instrucción. Por ejemplo, 32 bits sería:
#define log_2_32_ppc(x) (31-__cntlzw(x))
Si usted puede manejar un pequeño margen de error en los valores grandes que usted puede convertir a logaritmo en base 10 con unos pocos comandos:
#define log_10_estimate_32_ppc(x) (9-(((__cntlzw(x)*1233)+1545)>>12))
Este es específica de la plataforma y un poco impreciso, pero también implica sin ramas, división o conversión a punto flotante. Todo depende de lo que necesita.
Sólo sé las instrucciones ppc fuera de la mano, pero otras arquitecturas debería tener instrucciones similares.
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;
}
Esta es probablemente la forma más sencilla de resolver su problema, suponiendo que sólo se preocupan por dígitos antes del decimal y asumir nada menos que 10 está a sólo 1 dígito.
#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
)
)
);
}
Me gusta la respuesta de Ira Baxter. Aquí es una variante de plantilla que se encarga de los varios tamaños y se ocupa de los valores enteros máximo (actualizado para izar la comprobación de límite superior de la circular):
#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;
}
Para conseguir realmente el mejor desempeño de izar la prueba adicional fuera del circuito, es necesario especializarse max_decimal () para devolver constantes para cada tipo de su plataforma. Un compilador suficientemente magia podría optimizar la llamada a max_decimal () para una constante, pero la especialización es mejor con la mayoría de los compiladores de hoy. En su forma actual, esta versión es probablemente más lento porque max_decimal cuesta más que las pruebas retirados del bucle.
Voy a dejar todo eso como un ejercicio para el lector.
/// 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);
}
};
donde en powers_and_max hemos (10^n)-1 para todos n tal que
(10^n) < std::numeric_limits<type>::max()
y std::numeric_limits<type>::max() en una matriz:
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());
}
};
he aquí una prueba sencilla:
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);
Por supuesto que cualquier otra aplicación de un conjunto ordenado podría ser utilizado para powers_and_max y si había conocimiento de que no habría ninguna agrupación, pero el conocimiento de dónde puede estar el cluster tal vez un ajuste de auto aplicación de árboles podría ser mejor
manera eficaz
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;
}
Sin embargo, otro fragmento de código, haciendo básicamente lo mismo que Vitali, pero emplea búsqueda binaria. Powers matriz se perezoso inicializa una vez por instancia de tipo sin signo. Firmado sobrecarga tipo se encarga de signo menos.
#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 cualquiera cuida de una mayor optimización, tenga en cuenta que el primer elemento de la matriz de poderes no se usa nunca, y la l aparece con +1 2 veces.
en caso de que el número de dígitos Y se necesita el valor de cada posición de dígito uso esto:
int64_t = number, digitValue, digits = 0; // or "int" for 32bit
while (number != 0) {
digitValue = number % 10;
digits ++;
number /= 10;
}
digit le da el valor al número postition que se procesa actualmente en el bucle. por ejemplo, para el número 1776 es el valor del dígito:
6 en la primera bucle
7 en el segundo bucle
7 en la tercera bucle
1 en el cuarto bucle
C ++ 11 actualización de solución preferida:
#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;
}
impide instancias de plantilla con doble, 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);
}
Esto es lo que yo haría, si lo quieres para 10.Its de base bastante rápido y que prolly no conseguirá una pila overflock comprar enteros contando
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 más rápido es más eficiente, esto es una mejora con respecto a de Andrei Alexandrescu mejora . Su versión ya era más rápido que la forma ingenua (dividiendo por 10 en cada dígito). La versión a continuación es la constante de tiempo y más rápido, al menos en x86-64 y ARM para todos los tamaños, pero ocupa el doble de código binario, por lo que no es tan caché de usar.
Los puntos de referencia para esta versión vs versión de Alexandrescu en mi PR en Facebook locura .
Funciona en unsigned, no 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);
}
para enteros 'X' se quiere saber el número de dígitos, bien sin necesidad de utilizar ningún bucle, esta solución acto en una fórmula en una sola línea por lo que esta es la solución más óptima que he visto a este problema.
int x = 1000 ;
cout<<numberOfDigits = 1+floor(log10(x))<<endl ;
Esta es mi manera de hacerlo:
int digitcount(int n)
{
int count = 1;
int temp = n;
while (true)
{
temp /= 10;
if (temp != 0) ++count;
if (temp == 0) break;
}
return count;
}
Aquí hay un enfoque diferente:
digits = sprintf(numArr, "%d", num); // where numArr is a char array
if (num < 0)
digits--;
Esto puede no ser eficiente, pero es algo diferente a lo que sugieren otros.
