Maneira eficiente de determinar o número de dígitos em um número inteiro

144

Qual é uma maneira muito eficiente de determinar quantos dígitos existem em um número inteiro em C ++?

Seth
fonte
11
Em que base? 2? 10?
26630 Jacob Krall
2
Eu gostaria de fazê-lo na base 10
Seth
1
Uma vez fiz uma pergunta relacionada: como você pode obter o primeiro dígito em um int? Muitas das mesmas metodologias abaixo foram usadas nas respostas das pessoas. Aqui está o link, caso seja relevante para a sua tarefa [ stackoverflow.com/questions/701322/]
Dinah
A montagem em linha é qualificada?
György Andrasek 29/09/09
1
Embora todas essas respostas estejam em termos da base 10, é muito fácil alterar para calcular o resultado para qualquer base desejada.
Ira Baxter

Respostas:

106

Bem, a maneira mais eficiente, presumindo que você saiba o tamanho do número inteiro, seria uma pesquisa. Deve ser mais rápido que a abordagem baseada em logaritmo, muito mais curta. Se você não se importa em contar o '-', remova o + 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];
}
Vitali
fonte
5
Provavelmente mais rápido que minha resposta, bem feito. Para maior eficiência, se você souber que os números de entrada serão na maioria pequenos (suponho que sejam menos de 100.000), inverta os testes: if (x <10) retorne 1; se (x <100) retornar 2; etc., para que a função faça menos testes e saia mais rapidamente.
Squelart 28/09/09
29
Ou talvez reorganize e aninhe as instruções if para fazer uma pesquisa binária em vez de uma pesquisa linear.
precisa saber é o seguinte
1
Isso não é uma boa idéia. O que acontece quando a arquitetura se expande para números inteiros de 256 bits. Você precisa se lembrar de voltar e modificar este código. Na vida real, isso não acontecerá e, provavelmente, isso será usado para criar um buffer do tamanho correto, agora você está se abrindo para todos os tipos de problemas de buffer over-run em arquitetos maiores.
Martin York
3
assumindo uma distribuição uniforme de números, a pesquisa linear reversa (começando de dígitos máximos a 1) pode ser mais rápida, em média, do que a pesquisa binária, pois há muito mais números com dígitos N do que com dígitos N-1 graphics.stanford.edu/~ seander /…
fa.
6
Eu não me preocuparia muito com números inteiros de 256 ou 128 bits. A menos que você precise contar o número de elétrons no Universo (10 ^ 78 na última vez em que o fiz), 64 bits funcionarão muito bem. Máquinas de 32 bits duraram ~~ 15 anos. Eu acho que as máquinas de 64 bits durarão muito mais tempo. Para um número maior, a aritmética de multiprecisão será boa e duvido que a eficiência da contagem de dígitos da computação seja importante.
Ira Baxter
74

A maneira mais simples é fazer:

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

log10 é definido em <cmath>ou <math.h>. Você precisaria criar um perfil para ver se é mais rápido do que qualquer um dos outros postados aqui. Não tenho certeza de quão robusto isso é com relação à precisão do ponto de flutuação. Além disso, o argumento não é assinado como valores negativos e o log realmente não se mistura.

Skizz
fonte
7
Para entradas de 32 bits e flutuadores de 56 bits, isso provavelmente funciona. Se a entrada for longa (64 bits), os 56 bits do log de dupla precisão podem causar uma resposta errada nos casos de valores próximos a valores altos de 10 ^ n. Espere um problema acima de 2 ^ 50.
Ira Baxter
1
Há também a questão de quão precisas são as funções de log. Não verifiquei quão precisas elas são nas bibliotecas modernas e não me sentiria confortável cegamente confiando que elas seriam boas para uma parte em um bilhão.
David Thornley
@DavidThornley: log ou outras funções matemáticas são perfeitamente precisas, a menos que especificado na linha de comando do compilador. alguns serão convertidos para intrínsecos x86 em tempo de compilação. alguns não existem e se expandirão em fórmulas de intrínsecas existentes. por exemplo, se -fpfastvocê usar, poderá ver o uso de instrumentos SSE em vez de x87, o que gera menos garantia no IIRC de precisão. mas por padrão não há problema.
v.oddou
@DavidThornley: É mais do que precisão. A questão é se é garantido ou não esse log10 (10 ^ k) ≥ k para todos os k relevantes. Ou seja, é garantido que qualquer erro de arredondamento inevitável vá na direção certa. k + eps como resultado funciona, k - eps não. E "perfeitamente preciso" é ingênuo.
precisa saber é o seguinte
1
O teste i> 0 pode ser otimizado para i> 9
Pat
60

Talvez eu tenha entendido mal a pergunta, mas isso não acontece?

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)))))))));  
}  
Brad
fonte
29
E não ficaria surpreso se esta solução fosse a mais rápida.
VisioN
32
int digits = 0; while (number != 0) { number /= 10; digits++; }

Nota: "0" terá 0 dígitos! Se você precisar que 0 pareça ter 1 dígito, use:

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

(Obrigado Kevin Fegan)

No final, use um criador de perfil para saber quais das respostas aqui serão mais rápidas na sua máquina ...

esqueleto
fonte
3
Isso pode ou não ser mais rápido do que a abordagem de loop desenrolado que eu adotei - você precisaria definir o perfil da diferença (deve ser insignificante a longo prazo).
287/09 Vitali
Concordado, a criação de perfil é a única maneira de realmente ter certeza! Atualizei minha resposta com esse comentário, pois a resposta do teto de Ben S (log10 ()) desapareceu.
Squelart 28/09/09
11

Piada prática: Esta é a maneira mais eficiente (o número de dígitos é calculado em tempo de compilação):

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

Pode ser útil para determinar a largura necessária para o campo numérico na formatação, elementos de entrada etc.

blinnov.com
fonte
4
Primeiro, sua solução não funciona para 0. Segundo, sua solução não é aplicável ao caso geral de uma variável. Em terceiro lugar, se você estiver usando um literal constante, já sabe quantos dígitos ele possui.
287/09 Vitali
Também funciona para 0. Também funciona para qualquer base. O resto são pontos válidos que eu já descrevi.
Blinnov.com 29/09/09
3
Eu acho que não. Ele falha 0e também falha na base 1:) e gera erros de divisão por zero se a base for dada como 0. Pode ser corrigido embora. De qualquer forma, estou procurando um post muito antigo, desculpe, é só que acho que isso não precisa ser uma piada e pode realmente ser útil.
tjm
9

Veja Bit Twiddling Hacks para uma versão muito mais curta da resposta que você aceitou. Também tem o benefício de encontrar a resposta mais cedo se sua entrada for normalmente distribuída, verificando primeiro as grandes constantes. (v >= 1000000000)captura 76% dos valores, portanto, verificar se o primeiro será, em média, mais rápido.

Josh Haberman
fonte
Não está claro se o bit-twiddling é realmente mais rápido. Mesmo no pior dos casos, minha abordagem modificada requer 4 comparações (pode ser reduzida a 3 se eu examinar mais profundamente o particionamento, embora isso pareça improvável). Eu duvido seriamente que isso seja superado por operações aritméticas + cargas de memória (embora, se acessadas o suficiente, elas desaparecem no cache da CPU). Lembre-se, no exemplo que eles dão, eles também ocultam a base de log 2 como alguma função abstrata de IntegerLogBase2 (que na verdade não é barata).
217 Vitali
Apenas como acompanhamento, sim, se os números são normalmente distribuídos, a verificação em ordem é mais rápida. No entanto, ele tem o caso degenerado de ser duas vezes mais lento no pior caso. A abordagem particionada por número de dígitos, em vez do espaço de entrada, significa que o comportamento não possui um caso degenerado e sempre funciona de maneira otimizada. Além disso, lembre-se de que você está assumindo que os números serão distribuídos uniformemente. De fato, é mais provável que eles sigam alguma distribuição relacionada a <a href=" en.wikipedia.org/wiki/…> seria o meu palpite.
Vitali
Os hacks que rodam pouco não são mais rápidos que o método de partição acima, mas são potencialmente interessantes se você tiver um caso mais geral como um float aqui.
Corwin Joy
1
Os pequenos hacks sugerem uma maneira de obter o int log10, dado o int log2. Ele sugere várias maneiras de obter int log2, principalmente envolvendo poucas comparações / ramificações. (Acho que você está subestimando o custo de filiais imprevisíveis, Vitali). Se você pode usar o x86 asm embutido, a instrução BSR fornecerá o int log2 de um valor (ou seja, o índice de bits do bit de conjunto mais significativo). É um pouco lento no K8 (latência de 10 ciclos), mas rápido no Core 2 (latência de 2 ou 3 ciclos). Mesmo no K8, pode muito bem ser mais rápido que as comparações.
6269 Peter Cordes
No K10, lzcnt conta zeros à esquerda, portanto é quase o mesmo que bsr, mas uma entrada de 0 não é mais um caso especial com resultados indefinidos. Latências: BSR: 4, LZCNT: 2.
Peter Cordes
8

converter em string e, em seguida, usar funções internas

unsigned int i;
cout<< to_string(i).length()<<endl;
wugoat
fonte
7
int x = 1000;
int numberOfDigits = x ? static_cast<int>(log10(abs(x))) + 1 : 1;
bemaru
fonte
3
Embora isso seja eficiente em termos de LOCs, conforme observado na resposta aceita, o uso do log provavelmente não fornecerá o melhor desempenho.
Ian
@Ian Por que não? São apenas algumas instruções da FPU. Milhas melhor do que todos os ramos e laços em outras respostas.
Marquês de Lorne
5

Um pôster anterior sugeria um loop dividido por 10. Como as multiplicações nas máquinas modernas são muito mais rápidas, recomendo o seguinte código:

 int digits = 1, pten=10; while ( pten <= number ) { digits++; pten*=10; }
Ira Baxter
fonte
1
o diabo está nos detalhes - o que acontece com digamos std :: numeric_limits <int> :: número == max - ele pode ter um problema de terminação
pgast
2
Se você estiver preocupado com esse caso, poderá adicionar um IF adicional para lidar com valores muito grandes.
Ira Baxter
2
Devo observar que em máquinas x86, uma multiplicação por uma constante 10, conforme usada neste caso, pode realmente ser implementada pelo compilador como LEA R2, [8 * R1 + R1], ADD R1, R2, levando no máximo 2 relógios. As multiplicações por variáveis ​​levam dezenas de relógios e as divisões são muito piores.
Ira Baxter
a vantagem com a abordagem de divisão é que você não precisa se preocupar com números negativos.
Johannes Schaub - litb
1
Comparei a abordagem de multipicação (com um fabs para remover a questão do sinal) versus a abordagem de divisão. Na minha máquina, a abordagem de divisão é fator 2 mais lenta que a abordagem de multiplicação. Se isso é otimização prematura ou não, realmente depende de onde e como isso é chamado.
Spacemoose
5

A arquitetura ppc possui algumas instruções de contagem. Com isso, você pode determinar a base de log 2 de um número inteiro positivo em uma única instrução. Por exemplo, 32 bits seria:

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

Se você conseguir lidar com uma pequena margem de erro em valores grandes, poderá convertê-lo na base 10 do log com mais algumas instruções:

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

Isso é específico da plataforma e um pouco impreciso, mas também não envolve ramificações, divisão ou conversão em ponto flutuante. Tudo depende do que você precisa.

Conheço apenas as instruções ppc, mas outras arquiteturas devem ter instruções semelhantes.


fonte
Esta solução calcula log2 (15) = 4 bits e log2 (9) = 4 bits. Mas 15 e 9 exigem números diferentes de dígitos decimais para serem impressos. Portanto, não funciona, a menos que você não se importe com a impressão de números com muitos dígitos. Mas nesse caso, você sempre pode escolher "10" como a resposta para int.
Ira Baxter
Uau, uma função aproximada. Agradável.
precisa saber é o seguinte
4
 #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;
 }

Essa é provavelmente a maneira mais simples de resolver seu problema, supondo que você se preocupe apenas com dígitos antes do decimal e supondo que menos de 10 seja apenas 1 dígito.

RoryHector
fonte
1

Eu gosto da resposta de Ira Baxter. Aqui está uma variante de modelo que lida com os vários tamanhos e lida com os valores máximos inteiros (atualizados para elevar a verificação do limite superior do loop):

#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 realmente obter o desempenho aprimorado ao elevar o teste adicional para fora do loop, você precisa especializar max_decimal () para retornar constantes para cada tipo em sua plataforma. Um compilador suficientemente mágico pode otimizar a chamada para max_decimal () para uma constante, mas a especialização é melhor com a maioria dos compiladores hoje. Tal como está, esta versão é provavelmente mais lenta porque max_decimal custa mais do que os testes removidos do loop.

Vou deixar tudo isso como um exercício para o leitor.

janm
fonte
Você deseja fazer com que o limite superior verifique primeiro um estado condicional separado testado para não verificar em cada iteração do loop.
Ira Baxter
Você não quer colocar 10 nessa temperatura t. O compilador pode considerar que multiplicar por t é multiplicar por uma variável real e usar uma instrução de multiplicação de uso geral. Se você escreveu "result * = 10;" o compilador certamente notará a multiplicação pela constante 10 e implementará isso com alguns turnos e acréscimos, o que é extremamente rápido.
Ira Baxter
Se a multiplicação por t sempre foi multiplicada por 10, sim, o compilador poderia fazer a redução de força. No entanto, t não é invariável neste loop (é apenas uma modificação de uma função de potência inteira que eu tinha por aí). A otimização correta é a especialização no tipo retornando uma constante. No entanto, você está certo que, nesse caso, a função está sempre aumentando 10 para uma potência, não um número inteiro arbitrário para uma potência, e a redução de força oferece uma boa vitória. Então eu fiz uma mudança ... Desta vez, mais mudanças realmente são deixadas como um exercício! (Stack Overflow é um grande dissipador de tempo ...)
JANM
1
#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://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
            )
        )
    );
}
Adolfo
fonte
0

Outro trecho de código, fazendo basicamente o mesmo que o de Vitali, mas emprega pesquisa binária. A matriz Powers é inicializada com preguiça uma vez por instância do tipo não assinado. A sobrecarga do tipo assinado cuida do sinal de 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) );
}

Se alguém se preocupa com uma otimização adicional, observe que o primeiro elemento do conjunto de potências nunca é usado e laparece +1duas vezes.

Alexey Biryukov
fonte
0

caso seja necessário o número de dígitos E o valor de cada posição de dígito, use:

int64_t = number, digitValue, digits = 0;    // or "int" for 32bit

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

digitfornece o valor na publicação numérica atualmente processada no loop. por exemplo, para o número 1776, o valor do dígito é:
6 no 1º loop
7 no 2º loop
7 no 3º loop
1 no 4º loop

JFS
fonte
0
// 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) );
Adolfo
fonte
Correção para "Brincadeira prática" de 'blinnov.com' acima
Adolfo
0
/// 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
                )
            )
        )
    );
}
Adolfo
fonte
0

para o número inteiro 'X', você quer saber o número de dígitos, tudo bem, sem usar nenhum loop, esta solução atua apenas em uma fórmula em uma linha, portanto, esta é a solução mais ideal que já vi para esse problema.

 int x = 1000 ; 
 cout<<numberOfDigits = 1+floor(log10(x))<<endl ; 
Sameh Adel
fonte
Falha em INT_MAX e também em números negativos.
ranu
@ranu falha em INT_MAX como? Quando o argumento é convertido em double? Ou você está se referindo a alguma entrada inteira impossível com dígitos decimais INT_MAX? O que também falharia em todas as outras respostas aqui?
Marquês de Lorne
0
int numberOfDigits(int n){

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

Isso é o que eu faria, se você o quisesse para a base 10. É muito rápido e você provavelmente não obterá um overflock de pilha, contando números inteiros

Mc Stevens
fonte
0
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";
zwi3b3l404
fonte
0

Se mais rápido for mais eficiente, isso é uma melhoria na melhoria de andrei alexandrescu . Sua versão já era mais rápida que a ingênua (dividindo por 10 a cada dígito). A versão abaixo é de tempo constante e mais rápida, pelo menos, em x86-64 e ARM para todos os tamanhos, mas ocupa o dobro do código binário, por isso não é tão compatível com o cache.

Benchmarks para esta versão vs a versão de alexandrescu no meu PR no facebook folly .

Funciona unsigned, não 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);
}
Gabriel
fonte
0

Eu estava trabalhando em um programa que exigia que eu verifique se o usuário respondeu corretamente quantos dígitos há em um número, então tive que desenvolver uma maneira de verificar a quantidade de dígitos em um número inteiro. Acabou sendo uma coisa relativamente fácil de resolver.

double check=0, exponent=1000;

while(check<=1)
{
    check=number/pow(10, exponent);
    exponent--;
}

exponent=exponent+2;
cout<<exponent<<endl;

Isso acabou sendo minha resposta, que atualmente trabalha com números com menos de 10 ^ 1000 dígitos (pode ser alterada alterando o valor do expoente).

PS: Eu sei que essa resposta está dez anos atrasada, mas cheguei aqui em 2020 para que outras pessoas possam usá-la.

Daniel Bercero
fonte
-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);
    }
};

onde powers_and_maxtemos (10^n)-1para todos nque

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

e std::numeric_limits<type>::max()em uma 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());
   }
};

aqui está um teste simples:

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

É claro que qualquer outra implementação de um conjunto ordenado pode ser usada powers_and_maxe se havia conhecimento de que haveria armazenamento em cluster, mas nenhum conhecimento de onde o cluster poderia estar talvez uma implementação de árvore autoajustável poderia ser melhor

pgast
fonte
-1

forma efetiva

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;
}
Davit Siradeghyan
fonte
-1

Atualização em C ++ 11 da solução 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;
        }

previne instanciação de template com double, et. al.

gerardw
fonte
-1
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;
}
DPenner1
fonte
-2

Esta é a minha maneira de fazer isso:

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

        return count;
    }
Leonardo Urbano
fonte
2
enquanto true / síndrome de interrupção: D
Петър Петров
-1 é a mesma abordagem que a primeira resposta deu seis anos antes e não acrescenta nada (na verdade, é significativamente pior).
-4

Aqui está uma abordagem diferente:

digits = sprintf(numArr, "%d", num);    // where numArr is a char array
if (num < 0)
    digits--;

Isso pode não ser eficiente, apenas algo diferente do que os outros sugeriram.

Ashwin
fonte
4
O pedido foi extremamente eficiente. Isto é o oposto.
Ira Baxter