Cara efisien untuk menentukan jumlah digit dalam bilangan bulat

Apa cara yang sangat efisien untuk menentukan berapa digit yang ada dalam integer di C ++?

Nah, cara yang paling efisien, anggap Anda tahu ukuran bilangan bulat, akan menjadi pencarian. Harus lebih cepat daripada pendekatan berbasis logaritma yang jauh lebih pendek. Jika Anda tidak peduli tentang penghitungan '-', hapus +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];
}

Cara paling sederhana adalah dengan melakukan:

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

log10 didefinisikan dalam <cmath>atau <math.h>. Anda perlu membuat profil ini untuk melihat apakah ini lebih cepat daripada yang lain yang diposting di sini. Saya tidak yakin seberapa kuat ini dalam hal presisi float point. Juga, argumen tidak ditandatangani karena nilai negatif dan log tidak benar-benar tercampur.

Mungkin saya salah paham pertanyaannya tetapi tidakkah ini berhasil?

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

Catatan: "0" akan memiliki 0 digit! Jika Anda perlu 0 untuk memiliki 1 digit, gunakan:

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

(Terima kasih Kevin Fegan)

Pada akhirnya, gunakan profiler untuk mengetahui mana dari semua jawaban di sini yang akan lebih cepat di mesin Anda ...

Lelucon praktis: Ini adalah cara yang paling efisien (jumlah digit dihitung pada waktu kompilasi):

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

Mungkin bermanfaat untuk menentukan lebar yang diperlukan untuk bidang angka dalam pemformatan, elemen input dll.

Lihat Bit Twiddling Hacks untuk versi yang jauh lebih pendek dari jawaban yang Anda terima. Ini juga memiliki keuntungan menemukan jawaban lebih cepat jika input Anda terdistribusi normal, dengan memeriksa konstanta besar terlebih dahulu. (v >= 1000000000)menangkap 76% dari nilai, jadi memeriksa yang pertama rata-rata akan lebih cepat.

mengkonversi ke string dan kemudian menggunakan fungsi bawaan

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

int x = 1000;
int numberOfDigits = x ? static_cast<int>(log10(abs(x))) + 1 : 1;

Poster sebelumnya menyarankan loop yang membelah 10. Karena mengalikan pada mesin modern jauh lebih cepat, saya akan merekomendasikan kode berikut sebagai gantinya:

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

Arsitektur ppc memiliki instruksi penghitungan sedikit. Dengan itu, Anda dapat menentukan basis log 2 dari bilangan bulat positif dalam satu instruksi. Sebagai contoh, 32 bit adalah:

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

Jika Anda dapat menangani margin kesalahan kecil pada nilai besar, Anda dapat mengonversinya menjadi basis 10 dengan beberapa instruksi lain:

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

Ini adalah platform spesifik dan sedikit tidak akurat, tetapi juga tidak melibatkan cabang, divisi, atau konversi ke floating point. Semua tergantung pada apa yang Anda butuhkan.

Saya hanya tahu instruksi ppc begitu saja, tetapi arsitektur lain harus memiliki instruksi serupa.

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

Ini mungkin cara paling sederhana untuk menyelesaikan masalah Anda, dengan asumsi Anda hanya peduli pada digit sebelum desimal dan mengasumsikan apa pun yang kurang dari 10 hanya 1 digit.

Saya suka jawaban Ira Baxter. Berikut adalah varian templat yang menangani berbagai ukuran dan penawaran dengan nilai integer maksimum (diperbarui untuk mengerek pemeriksaan batas atas dari 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;
}

Untuk benar-benar mendapatkan peningkatan kinerja dari mengangkat tes tambahan dari loop, Anda perlu mengkhususkan max_decimal () untuk mengembalikan konstanta untuk setiap jenis pada platform Anda. Kompiler ajaib yang cukup dapat mengoptimalkan panggilan ke max_decimal () ke konstan, tetapi spesialisasi lebih baik dengan sebagian besar kompiler saat ini. Seperti berdiri, versi ini mungkin lebih lambat karena biaya max_decimal lebih dari tes yang dihapus dari loop.

Saya akan meninggalkan semua itu sebagai latihan untuk pembaca.

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

Namun potongan kode lain, yang pada dasarnya sama dengan Vitali tetapi menggunakan pencarian biner. Array Powers malas diinisialisasi sekali per instance tipe yang tidak ditandatangani. Jenis berlebih yang ditandatangani menangani tanda minus.

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

Jika ada yang peduli dengan optimasi lebih lanjut, harap perhatikan bahwa elemen pertama array kekuasaan tidak pernah digunakan, dan lmuncul dengan +12 kali.

dalam hal jumlah digit DAN nilai setiap posisi digit diperlukan gunakan ini:

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

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

digitmemberi Anda nilai pada posisi nomor yang saat ini diproses dalam loop. misalnya untuk angka 1776 nilai digit adalah:
6 di loop 1
7 di loop 2
7 di loop ke-3
1 di loop ke-4

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

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

untuk integer 'X' Anda ingin tahu jumlah digit, baiklah tanpa menggunakan loop apa pun, solusi ini bertindak dalam satu rumus hanya dalam satu baris jadi ini adalah solusi paling optimal yang pernah saya lihat untuk masalah ini.

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

int numberOfDigits(int n){

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

Inilah yang akan saya lakukan, jika Anda menginginkannya untuk basis 10. Cukup cepat dan Anda tidak akan mendapatkan tumpukan overflock penghitungan bilangan bulat

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

Jika lebih cepat lebih efisien, ini merupakan peningkatan pada perbaikan andrei alexandrescu . Versinya sudah lebih cepat dari cara naif (membaginya dengan 10 pada setiap digit). Versi di bawah ini adalah waktu yang konstan dan lebih cepat setidaknya pada x86-64 dan ARM untuk semua ukuran, tetapi menempati kode biner dua kali lebih banyak, sehingga tidak ramah-cache.

Tolak ukur untuk versi ini vs versi alexandrescu pada PR saya di facebook kebodohan .

Bekerja unsigned, bukan 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);
}

Saya sedang mengerjakan sebuah program yang mengharuskan saya untuk memeriksa apakah pengguna menjawab dengan benar berapa banyak digit dalam suatu angka, jadi saya harus mengembangkan cara untuk memeriksa jumlah digit dalam bilangan bulat. Akhirnya menjadi hal yang relatif mudah dipecahkan.

double check=0, exponent=1000;

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

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

Ini akhirnya menjadi jawaban saya yang saat ini bekerja dengan angka dengan kurang dari 10 ^ 1000 digit (dapat diubah dengan mengubah nilai eksponen).

PS Saya tahu jawaban ini terlambat sepuluh tahun tetapi saya tiba di sini pada tahun 2020 sehingga orang lain mungkin menggunakannya.

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

di mana powers_and_maxkita miliki (10^n)-1untuk semua nitu

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

dan std::numeric_limits<type>::max()dalam sebuah 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());
   }
};

inilah tes sederhana:

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

Tentu saja implementasi lain dari himpunan yang diperintahkan mungkin digunakan untuk powers_and_maxdan jika ada pengetahuan bahwa akan ada pengelompokan tetapi tidak ada pengetahuan tentang di mana kluster itu mungkin implementasi pohon penyesuaian diri mungkin yang terbaik

cara yang efektif

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

Pembaruan C ++ 11 dari solusi yang disukai:

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

mencegah instantiasi template dengan 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;
}

Inilah cara saya untuk melakukan itu:

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

        return count;
    }

Berikut pendekatan yang berbeda:

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

Ini mungkin tidak efisien, hanya sesuatu yang berbeda dari yang disarankan orang lain.