确定整数位数的有效方法

在 C + + 中，确定一个整数中有多少个数字的非常 有效率的方法是什么？

279404 次浏览
小开 
int digits = 0; while (number != 0) { number /= 10; digits++; }

注意: “0”将有0个数字! 如果你需要0来显示有1个数字，使用:

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

(谢谢 Kevin Fegan)

最后，使用分析器来知道在你的机器上，这里的所有答案中哪一个会更快..。

小开
最佳答案

假设你知道整数的大小，最有效的方法就是查找。应该比基于对数的方法快得多。如果您不关心计数’-’，删除 + 1。

#include <climits>


// 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 64-bit numbers
template <>
int numDigits(int64_t x) {
if (x == INT64_MIN) return 19 + 1;
if (x < 0) return digits(-x) + 1;


if (x >= 10000000000) {
if (x >= 100000000000000) {
if (x >= 10000000000000000) {
if (x >= 100000000000000000) {
if (x >= 1000000000000000000)
return 19;
return 18;
}
return 17;
}
if (x >= 1000000000000000)
return 16;
return 15;
}
if (x >= 1000000000000) {
if (x >= 10000000000000)
return 14;
return 13;
}
if (x >= 100000000000)
return 12;
return 11;
}
if (x >= 100000) {
if (x >= 10000000) {
if (x >= 100000000) {
if (x >= 1000000000)
return 10;
return 9;
}
return 8;
}
if (x >= 1000000)
return 7;
return 6;
}
if (x >= 100) {
if (x >= 1000) {
if (x >= 10000)
return 5;
return 4;
}
return 3;
}
if (x >= 10)
return 2;
return 1;
}


// partial specialization optimization for 32-bit numbers
template<>
int numDigits(int32_t x)
{
if (x == INT32_MIN) 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];
}
小开

最简单的方法是:

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

Log10在 <cmath>或 <math.h>中定义。你需要对这个进行侧写，看看它是否比这里发布的任何一个都要快。我不确定这对于浮点精度来说有多稳健。此外，参数是无符号的，因为负值和日志实际上并不混合。

小开

之前的一张海报建议使用一个除以10的循环。 由于现代机器上的乘法速度要快得多，我建议改用以下代码:

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

恶作剧: 这是 的最有效的方法(编译时计算位数) :

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

可能有助于确定数字字段在格式、输入元素等方面所需的宽度。

小开

这里有一个不同的方法:

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

这可能效率不高，只是与其他人的建议有所不同。

小开

请参阅 有点小技巧以获得您接受的答案的更短版本。如果您的输入是正态分布的，它还有一个好处，那就是通过首先检查较大的常量，可以更快地找到答案。(v >= 1000000000)捕获76% 的值，因此平均来说，首先检查会更快。

小开

我喜欢 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 _ decal ()来返回平台上每种类型的常量。一个足够神奇的编译器可以优化对一个常量 max _ decal ()的调用，但是当今大多数编译器的专门化更好。实际上，这个版本可能更慢，因为 max _ decal 的成本比从循环中删除的测试要高。

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

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

在 powers_and_max中，我们在哪里有 (10^n)-1对所有 n这样

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

和 std::numeric_limits<type>::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());
}
};

这里有一个简单的测试:

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

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

小开

Ppc 体系结构有一个位计数指令。这样，您就可以在一条指令中确定正整数的日志基数2。例如，32位是:

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

如果你能处理大值时的小误差，你可以用另外一些指令将它转换为以10为基数的日志:

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

这是平台特有的，稍有不准确，但也涉及到没有分支，划分或转换为浮点数。取决于你需要什么。

我只知道现成的 ppc 指令，但其他体系结构应该有类似的指令。

小开

有效的方法

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

也许我误解了这个问题，但是这样不就行了吗？

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

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

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

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

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

如果有人关心进一步的优化，请注意，第一个元素的幂阵列从来没有使用，和 l出现与 +12次。

小开

如果需要数字 还有，则每个数字位置的值如下:

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


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

digit给出当前在循环中处理的数字位置的值。例如，数字1776的数值是:
第一圈是6
第二圈7分
第三圈是7
第四圈1

小开

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

用 double 等阻止模板实例化。

小开 
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;
}
小开 
// 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) );
小开 
#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 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
)
)
);
}
小开 
/// Determine the number of digits for a 64 bit integer.
/// - Uses at most 5 comparisons.
/// - (cX) 2014 adolfo.dimare@gmail.com
/// - \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
)
)
)
);
}
小开

这就是我的方法:

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


return count;
}
小开

对于整数‘ X’，你想知道数字的个数，好的，不用任何循环，这个解决方案只用一行中的一个公式，所以这是我见过的最优的解决方案。

 int x = 1000 ;
cout<<numberOfDigits = 1+floor(log10(x))<<endl ;
小开 
 #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的数字都只是1位数。

小开 
int numberOfDigits(int n){


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

如果你想要10进制的话，我会这么做。它非常快，你很可能不会得到一个堆叠群购买计数整数

小开 
int x = 1000;
int numberOfDigits = x ? static_cast<int>(log10(abs(x))) + 1 : 1;
小开 
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";
小开

如果速度越快效率越高，这是对 Andrei Alexandrescu 的改善的一个改进。他的版本已经比天真的方法快(每个数字除以10)。下面的版本是固定时间和更快，至少在 x86-64和 ARM 的所有大小，但占用两倍的二进制代码，所以它不是缓存友好。

这个版本的基准与我的 Facebook 上的公关蠢事上的 Alexandrescu 版本相比。

在 unsigned上工作，不是在 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);
}
小开

我当时正在开发一个程序，它要求我检查用户是否正确地回答了一个数字中有多少个数字，所以我必须开发一种方法来检查一个整数中的数字数量。结果这是一个相对容易解决的问题。

double check=0, exponent=1000;


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


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

这最终成为我的答案，目前工作的数字少于10 ^ 1000位(可以改变指数的值)。

附言。 我知道这个答案晚了十年，但我是在2020年来到这里的，所以其他人可能会使用它。

小开

控制台输出样品

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;
小开

使用最好的和有效的方法的 Log10(n)的方法，它给你在短短的 对数时间所期望的结果。

对于负数 腹肌将其转换为正数，而对于数 0，如果条件将阻止您继续进行，并将输出打印为 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;
}
小开

可以使用这个递归函数，当它的参数大于或等于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
小开

这里有一个巧妙的技巧，使用事实，intLog2是容易和快速的: log10(x) = log2(x)/log2(10)。四舍五入的问题必须加以考虑。

小样

constexpr int intPow(int base, int n) {
int result = 1;
while (n) {
if (n & 1 == 1)
result *= base;
base *= base;
n >>= 1;
}
return result;
}


constexpr int intLog2(int x) {
int result = -1;
while (x) {
x >>= 1;
++result;
}
return result;
}


constexpr int intLog10(int x) {
constexpr int powersOf10[]{1,         10,        100,     1000,
10000,     100000,    1000000, 10000000,
100000000, 1000000000};
auto aprox = (intLog2(x) + 1) * 1233 >> 12;
return aprox - (x < powersOf10[aprox]);
}

所有的操作都是在整数上完成的。没有划分，所以应该非常快，但查找表可能更快(可能会为此提供基准)。

小开

你可以用这个来计算 编译时上的数字数:

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: : Integralauto”改为“ long long”。

注意: 如果您希望负数中的负号也被计数，那么将 -9改为0;

用法例子:

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

这种方法的工作原理是将一个数字递归除以10，直到它变成一个单位数字，在这种情况下，我们将 + 1加到总和中。


提交答案