确定整数中位数的有效方法

What is a very efficient way of determining how many digits there are in an integer in C++?

什么是一个非常有效的方法来确定在一个整数中有多少位数字在c++中?

24 个解决方案

#1

Well, the most efficient way, presuming you know the size of the integer, would be a lookup. Should be faster than the much shorter logarithm based approach. If you don't care about counting the '-', remove the + 1.

如果你知道整数的大小，最有效的方法就是查找。应该比更短的基于对数的方法要快。如果你不关心计算“-”，删除+ 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];
}

#2

The simplest way is to do:

最简单的方法是:

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

log10 is defined in <cmath> or <math.h>. You'd need to profile this to see if it's faster than any of the others posted here. I'm not sure how robust this is with regards to float point precision. Also, the argument is unsigned as negative values and log don't really mix.

log10在 或 中定义。你需要对它进行剖析，看看它是否比这里发布的任何其他文件都要快。对于浮点精度，我不确定它有多健壮。而且，参数是无符号的，为负值，而log不是混合。

#3

Perhaps I misunderstood the question but doesn't this do it?

也许我误解了这个问题，但这不是真的吗?

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

#4

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

Note: "0" will have 0 digits! If you need 0 to appear to have 1 digit, use:

注意:“0”将有0位!如果你需要0看起来有1位数字，请使用:

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

(Thanks Kevin Fegan)

(感谢凯文·费根)

In the end, use a profiler to know which of all the answers here will be faster on your machine...

最后，使用一个分析器来知道在你的机器上哪个答案会更快……

#5

Practical joke: This is the most efficient way (number of digits is calculated at compile-time):

实用笑话:这是最有效的方法(位数在编译时计算):

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

May be useful to determine the width required for number field in formatting, input elements etc.

可以用来确定格式、输入元素等中的数字字段所需的宽度。

#6

See Bit Twiddling Hacks for a much shorter version of the answer you accepted. It also has the benefit of finding the answer sooner if your input is normally distributed, by checking the big constants first. (v >= 1000000000) catches 76% of the values, so checking that first will on average be faster.

有关您所接受的答案的更短版本，请参阅Bit twitthacks。如果输入是正态分布的话，它还可以通过首先检查大常数来更快地找到答案。(v >= 1000000000)捕获76%的值，因此检查第一个值平均会更快。

#7

convert to string and then use built-in functions

转换为字符串，然后使用内置函数。

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

#8

A previous poster suggested a loop that divides by 10. Since multiplies on modern machines are a lot faster, I'd recommend the following code instead:

之前的一张海报建议用一个圈除以10。由于现代机器上的乘法运算要快得多，所以我推荐以下代码:

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

#9

The ppc architecture has a bit counting instruction. With that, you can determine the log base 2 of a positive integer in a single instruction. For example, 32 bit would be:

ppc架构有一个位计数指令。这样，您就可以在一条指令中确定一个正整数的log以2为底的对数。例如，32位是:

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

If you can handle a small margin of error on large values you can convert that to log base 10 with another few instructions:

如果你能在大的值上处理小的误差，你可以把它转换成以10为底的对数。

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

This is platform specific and slightly inaccurate, but also involves no branches, division or conversion to floating point. All depends on what you need.

这是平台特有的，有点不准确，但也不涉及分支、分割或转换到浮点数。一切都取决于你需要什么。

I only know the ppc instructions off hand, but other architectures should have similar instructions.

我现在只知道ppc指令，但是其他架构应该有类似的指令。

#10

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

This is probably the simplest way of solving your problem, assuming you only care about digits before the decimal and assuming anything less than 10 is just 1 digit.

这可能是解决问题的最简单的方法，假设你只关心小数点前的数字，假设小于10的都是1位数。

#11

#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 [e-mail]
/// - \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
            )
        )
    );
}

#12

I like Ira Baxter's answer. Here is a template variant that handles the various sizes and deals with the maximum integer values (updated to hoist the upper bound check out of the loop):

我喜欢Ira Baxter的答案。这里有一个模板变量，它处理各种大小，并处理最大整数值(更新后，将上界检查从循环中取出):

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

To actually get the improved performance from hoisting the additional test out of the loop, you need to specialise max_decimal() to return constants for each type on your platform. A sufficiently magic compiler could optimise the call to max_decimal() to a constant, but specialisation is better with most compilers today. As it stands, this version is probably slower because max_decimal costs more than the tests removed from the loop.

为了从循环中提升额外的测试来获得更好的性能，您需要专门指定max_decimal()来为平台上的每种类型返回常量。一个足够神奇的编译器可以将对max_decimal()的调用优化为常量，但是现在大多数编译器都更擅长专门化。按照目前的情况，这个版本可能比较慢，因为max_decimal比从循环中删除的测试花费更多。

I'll leave all that as an exercise for the reader.

我把这些留给读者作为练习。

#13

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

#14

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

where in powers_and_max we have (10^n)-1 for all n such that

在powers_and_max(10 ^ n)1对所有n这样

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

(10 ^ n)< std::numeric_limits <类型> ::max()

and std::numeric_limits<type>::max() in an array:

std::numeric_limit ::max()在数组中:

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

here's a simple 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);

Of course any other implementation of an ordered set might be used for powers_and_max and if there was knowledge that there would be clustering but no knowledge of where the cluster might be perhaps a self adjusting tree implementation might be best

当然，任何有序集的其他实现都可以用于powers_and_max，如果知道会有集群，但不知道集群可能位于何处，那么最好使用自调整树实现

#15

effective way

有效的方法

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

#16

Yet another code snippet, doing basically the same as Vitali's but employs binary search. Powers array is lazy initialized once per unsigned type instance. Signed type overload takes care of minus sign.

另一个代码片段，与Vitali的代码片段基本相同，但使用了二进制搜索。每个无符号类型实例初始化一次。符号类型重载处理负号。

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

If anybody cares of further optimization, please note that the first element of powers array is never used, and the l appears with +1 2 times.

如果有人关心进一步的优化，请注意，从来没有使用第一个元素的权力数组，和l出现+1 2次。

#17

in case the number of digits AND the value of each digit position is needed use this:

如果需要数字的数量和每个数字位置的值，请使用以下方法:

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

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

digit gives you the value at the number postition which is currently processed in the loop. for example for the number 1776 the digit value is:
6 in the 1st loop
7 in the 2nd loop
7 in the 3rd loop
1 in the 4th loop

数字显示当前在循环中处理的数字postition的值。例如，对于数字1776，数字的值是:在第一个循环第6个循环第7个循环第2个循环第7个循环第4个循环第3个循环第1个循环第6个循环第7个循环第7个循环

#18

C++11 update of preferred solution:

c++ 11首选解决方案更新:

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

prevents template instantiation with double, et. al.

防止模板实例化的双重，等等。

#19

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

#20

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

#21

int numberOfDigits(int n){

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

This is what i would do, if you want it for base 10.Its pretty fast and you prolly wont get a stack overflock buy counting integers

这就是我要做的，如果你想让它以10为基底。它的速度非常快，而且你可能不会得到一个堆栈溢出购买计数整数

#22

for integer 'X' you want to know the number of digits , alright without using any loop , this solution act in one formula in one line only so this is the most optimal solution i have ever seen to this problem .

对于整数“X”你想知道数字的个数，好吧，不用任何循环，这个解只作用于一行中的一个公式所以这是这个问题我见过的最优解。

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

#23

This is my way to do that:

这是我的方法:

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

        return count;
    }

#24

Here's a different approach:

这里有一个不同的方法:

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

This may not be efficient, just something different than what others suggested.

这可能不是有效的，只是不同于其他人的建议。