logo标签列表

高效确定整数位数的方法

c++integerdigits
169

在C++中，确定整数有多少位的非常高效的方法是什么？

14
以哪个进制呢？2进制？还是10进制？ - Jacob Krall
4
我想用十进制来做。 - Seth
1
我曾经问过一个相关的问题：如何获取int中的第一个数字？许多与下面相同的方法都被用在人们的答案中。如果这对你的任务有帮助，这是链接[https://dev59.com/pnRB5IYBdhLWcg3wJklC]。 - Dinah
1
虽然所有这些答案都是以十进制为基础的，但很容易更改以计算任何所需基数的结果。 - Ira Baxter
2
你对效率的衡量标准是什么？选项包括代码大小最小化、CPU周期数量、甚至结果的准确性。但每个选项都需要以不同的方式进行操作。而且，你指的是十进制数字、八进制数字、十六进制数字还是其他什么东西？ - Peter
显示剩余4条评论
33个回答
4
您可以使用此方法在编译时计算数字的数量： C++20 解决方案：
template<std::integral auto num>
constexpr int number_of_digits = num >= -9 && num <= 9 ? 1 : 1 + number_of_digits<num / 10>;

适用于负数、零和正数。

注意：若要使其与C++14兼容，请将“std::integral auto”更改为“long long”。

注意：如果您希望在负数中包括减号，则将-9更改为0；

使用示例：

int k = number_of_digits<101>; // k = 3

这个过程的运作方式是将一个数字递归地除以10，直到它变成一位数字，此时我们通过将总和加上1来完成。
有趣！这对浮点数和双精度浮点数也适用吗？我的问题是，我需要计算浮点数的位数，FLOAT_MIN/MAX 的尾数有 64 位！大多数实现在其他实现中都失败了。 - Tom Tom
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;
 }

假设你只关心小数点前的数字，而且任何小于10的数都只算一位数字，那么这可能是解决你问题最简单的方法。

2
如果速度更快就更高效，这是对Andrei Alexandrescu的改进的改进。他的版本已经比朴素方法（每个数字除以10）更快了。下面的版本在所有大小上至少在x86-64和ARM上都是恒定时间且更快，但它占用的二进制代码是原来的两倍，所以不太适合缓存友好型。
我的Facebook Folly PR上此版本与Alexandrescu版本的基准测试。
仅适用于无符号变量，而不是有符号变量。
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);
}
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 adolfo.dimare@gmail.com
/// - \see https://dev59.com/zXI_5IYBdhLWcg3wMf5_
/**  #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
            )
        )
    );
}
1

使用最佳和高效的 log10(n) 方法，可以在仅 对数时间 内获得所需的结果。

对于负数，abs()将其转换为正数；对于数字 0，if条件将停止您继续进行并将输出打印为 0 。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n; std::cin >> n;
    if(n)
        std::cout << floor(log10(abs(n))+1) << std::endl;
    else
        std::cout << 0 << std::endl;
    return 0;
}
1

我喜欢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;
}

为了从循环中提取额外的测试并获得改进的性能，您需要将max_decimal()专门化以返回平台上每种类型的常量。足够神奇的编译器可以将对max_decimal()的调用优化为常量，但是在今天大多数编译器中，专门化更好。就目前而言，这个版本可能会更慢，因为max_decimal的成本比从循环中删除的测试要高。
我会把所有这些留给读者作为练习。
你想将上限检查作为一个单独的条件首先进行测试，这样你就不需要在每次循环迭代中都进行检查。 - Ira Baxter
你不想把10放进那个临时变量t里。编译器可能会认为乘以t是乘以一个实数变量，并使用通用的乘法指令。如果你改写成"result*=10;"，编译器肯定会注意到常数10的乘法并用几次移位和加法来实现，这样非常快速。 - Ira Baxter
如果t的乘法始终是乘以10，那么编译器可以进行强度降低。然而，在这种情况下，t不是循环不变量（它只是我手头上一个整数幂函数的修改）。正确的优化是针对返回常量的类型进行专门化。但是，你是正确的，在这种情况下，该函数总是将10提高到幂次方，而不是将任意整数提高到幂次方，因此强度降低会带来良好的效果。所以我做了一个改变...这一次进一步的更改真的留作练习！（Stack Overflow是一个巨大的时间浪费...） - janm
1

样例控制台输出

long long num = 123456789;
int digit = 1;
int result = 1;

while (result != 0) 
{
    result = num / 10;
    if (result != 0)
    {
        ++digit;
    }
    num = result;
}

cout << "Your number has " << digit << "digits" << endl;
最好将解决方案制作成一个函数。您还可以将示例输出作为文本包含在内。 - U. Windl
0
// Meta-program to calculate number of digits in (unsigned) 'N'.    
template <unsigned long long N, unsigned base=10>
struct numberlength
{   // https://dev59.com/zXI_5IYBdhLWcg3wMf5_
    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) );
以上来自 'blinnov.com' 的“恶作剧”已经得到更正。 - Adolfo
0
/// Determine the number of digits for a 64 bit integer.
/// - Uses at most 5 comparisons.
/// - (cX) 2014 adolfo.dimare@gmail.com
/// - \see https://dev59.com/zXI_5IYBdhLWcg3wMf5_
/**  #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
                )
            )
        )
    );
}
0
你可以使用这个递归函数，当它的参数大于或等于10时，就会调用自身。
int numDigits(int n) {
    return n >= 10 ? numDigits(n / 10) + 1 : 1;
}

使用示例：

#include <iostream>

int numDigits(int n) {
    return n >= 10 ? numDigits(n / 10) + 1 : 1;
}

int main() {
    int values[] = {0, 4, 10, 43, 789, 1500};
    for (int n : values) {
        std::cout << n << ": " << numDigits(n) << '\n';
    }
    return 0;
}

输出：

0: 1
4: 1
10: 2
43: 2
789: 3
1500: 4
好的，但速度不够快，并且（像许多其他程序一样）在浮点数FLOAT_MAX时失败。 - Tom Tom
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接