separar - invertir un numero en c++ recursivo

Manera eficiente de determinar la cantidad de dígitos en un entero

Question

¿Cuál es una forma muy eficiente de determinar cuántos dígitos hay en un entero en C ++?

Answer 1

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, solo algo diferente de lo que otros sugirieron.

Answer 2

Broma práctica: esta es la forma más eficiente (el 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 el ancho requerido para el campo numérico en el formato, elementos de entrada, etc.

Answer 3

Bueno, la forma más eficiente, suponiendo que conozcas el tamaño del entero, sería una búsqueda. Debería ser más rápido que el enfoque basado en el logaritmo mucho más corto. Si no te importa contar el ''-'', elimina 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];
}

Answer 4

C ++ 11 actualización de la 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;
        }

evita la creación de instancias de plantillas con double, et. Alabama.

Answer 5

Esta es mi manera de hacer eso:

   int digitcount(int n)
    {
        int count = 1;
        int temp = n;
        while (true)
        {
            temp /= 10;
            if (temp != 0) ++count;
            if (temp == 0) break;
        }

        return count;
    }

Answer 6

La arquitectura ppc tiene una instrucción de conteo de bits. Con eso, puede determinar la base de registro 2 de un entero positivo en una sola instrucción. Por ejemplo, 32 bit sería:

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

Si puede manejar un pequeño margen de error en valores grandes, puede convertir eso a log base 10 con otras pocas instrucciones:

#define log_10_estimate_32_ppc(x) (9-(((__cntlzw(x)*1233)+1545)>>12))

Esto es específico de la plataforma y ligeramente inexacto, pero también no implica ramas, división o conversión a coma flotante. Todo depende de lo que necesites

Solo conozco las instrucciones de ppc, pero otras arquitecturas deberían tener instrucciones similares.

Answer 7

La forma más simple es hacer:

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

log10 se define en <cmath> o <math.h> . Tendría que crear un perfil para ver si es más rápido que cualquiera de los otros publicados aquí. No estoy seguro de cuán robusto es esto con respecto a la precisión del punto flotante. Además, el argumento no está firmado ya que los valores negativos y el log realmente no se mezclan.

Answer 8

Me gusta la respuesta de Ira Baxter. Aquí hay una variante de plantilla que maneja los distintos tamaños y se ocupa de los valores enteros máximos (actualizados para elevar la verificación del límite superior del bucle):

#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 obtener realmente el rendimiento mejorado de elevar la prueba adicional fuera del ciclo, debe especializar max_decimal () para devolver las constantes para cada tipo en su plataforma. Un compilador suficientemente mágico podría optimizar la llamada a max_decimal () a una constante, pero la especialización es mejor con la mayoría de los compiladores de hoy. Tal como está, esta versión es probablemente más lenta porque max_decimal cuesta más que las pruebas eliminadas del ciclo.

Dejaré todo eso como un ejercicio para el lector.

Answer 9

Otro fragmento de código más, que hace básicamente lo mismo que Vitali, pero emplea la búsqueda binaria. La matriz Powers se inicializa perezosamente una vez por instancia de tipo sin firmar. La sobrecarga de tipo firmada se ocupa del 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 alguien se preocupa por una mayor optimización, tenga en cuenta que el primer elemento del conjunto de potencias nunca se utiliza, y el l aparece con +1 2 veces.

Answer 10

Tal vez entendí mal la pregunta, pero ¿no lo hace?

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

Answer 11

Un póster anterior sugirió un bucle que se divide entre 10. Como las multiplicaciones en máquinas modernas son mucho más rápidas, recomendaría el siguiente código:

 int digits = 1, pten=10; while ( pten <= number ) { digits++; pten*=10; }

Answer 12

Vea Bit Twiddling Hacks para una versión mucho más corta de la respuesta que ha aceptado. También tiene la ventaja de encontrar la respuesta más pronto si su entrada se distribuye normalmente, primero verificando las constantes grandes. (v >= 1000000000) capta el 76% de los valores, por lo que comprobar que el primero será, en promedio, más rápido.

Answer 13

convertir a cadena y luego usar funciones incorporadas

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

Answer 14

en caso de que se necesite el número de dígitos Y el valor de cada posición de dígito, use 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 en la posición numérica que se procesa actualmente en el ciclo. por ejemplo, para el número 1776, el valor del dígito es:
6 en el primer ciclo
7 en el segundo ciclo
7 en el tercer ciclo
1 en el 4º bucle

Answer 15

manera efectiva

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

Answer 16

para la ''X'' entera, quiere saber el número de dígitos, está bien sin usar ningún bucle, esta solución actúa en una fórmula en una sola línea, por lo que esta es la solución más óptima que he visto para este problema.

 int x = 1000 ; 
 cout<<numberOfDigits = 1+floor(log10(x))<<endl ; 

Answer 17

 #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 simple de resolver su problema, suponiendo que solo le interesan los dígitos antes del decimal y suponiendo que algo inferior a 10 es solo 1 dígito.

Answer 18

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

Answer 19

// Meta-program to calculate number of digits in (unsigned) ''N''.    
template <unsigned long long N, unsigned base=10>
struct numberlength
{   // http://.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) );

Answer 20

/// Determine the number of digits for a 64 bit integer.
/// - Uses at most 5 comparisons.
/// - (cX) 2014 [email protected]
/// - /see http://.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
                )
            )
        )
    );
}

Answer 21

int digits = 0; while (number != 0) { number /= 10; digits++; }

Nota: "0" tendrá 0 dígitos! Si necesita que 0 parezca tener 1 dígito, use:

int digits = 0; do { number /= 10; digits++; } while (number != 0);

(Gracias Kevin Fegan)

Al final, use un generador de perfiles para saber cuál de todas las respuestas aquí será más rápida en su máquina ...

Answer 22

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

Answer 23

int numberOfDigits(int n){

    if(n<=9){
        return 1;
    }
    return 1 + numberOfDigits(n/10);
}

Esto es lo que haría, si lo quieres para la base 10. Es bastante rápido y no obtendrás una pila overflock comprar contando enteros

Answer 24

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 tenemos (10^n)-1 para todo 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());
   }
};

aquí hay una prueba 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);

Por supuesto, cualquier otra implementación de un conjunto ordenado podría usarse para powers_and_max y, si existiera conocimiento de que habría clustering pero no conocimiento de dónde podría estar el clúster, quizás una implementación de árbol autoajustable sea la mejor.