计算位数 – 哪种方法最有效？
有一种以上的解决方案可以找到给定数字中的数字位数。
例如：
方法1：
int findn(int num) { char snum[100]; sprintf(snum, "%d", num); return strlen(snum); } 方法2：
int findn(int num) { if (num == 0) return 1; int n = 0; while(num) { num /= 10; n++; } return n; }
方法-3：
int findn(int num) { /* math.h included */ return (int) log10(num) + 1; }
问题是 – 什么是最有效的方法？ 我知道方法-2是O(n)但是方法1和方法3呢？ 如何找到库函数的运行时复杂性？
以下更有效：
int findn(int num) { if ( num < 10 ) return 1; if ( num < 100 ) return 2; //continue until max int }
您可以通过二进制搜索进一步优化这一点，但那将是过度的。
GCC / Clang __builtin_clz()或Microsoft Visual C _BitScanReverse()内部函数在许多机器上编译为单个机器指令。 您可以将其用作O（1）解决方案的基础。 这是一个32位的实现：
#include #include /* Return the number of digits in the decimal representation of n. */ unsigned digits(uint32_t n) { static uint32_t powers[10] = { 0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, }; static unsigned maxdigits[33] = { 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, }; unsigned bits = sizeof(n) * CHAR_BIT - __builtin_clz(n); unsigned digits = maxdigits[bits]; if (n < powers[digits - 1]) { -- digits; } return digits; }
按照目前的情况，接受且最高度认可的答案对于负数仍然是不正确的。 如果回答者花时间测试它并发现它已被打破为负数，他可能会浪费更多的时间而不是机器通过简单地使用snprintf ，即
int count_digits(int arg) { return snprintf(NULL, 0, "%d", arg) - (arg < 0); }
我们不再是20世纪80年代了; 像我们一样停止编码。 我是一个C级标准狂热者，我最喜欢的答案是陶峰的答案 ......但即使这样也没有说明为什么它是目前为止最有效的答案; 在这个答案中，我打算通过考虑以下因素来表明他的答案可以进一步改善：
- 程序员的工作效率比代码效率更重要，因为与几分钟的运行时间相比，编写和测试新函数几乎肯定会花费更多的时间。
- 重用其他程序常用的相同标准库函数（可能）将这些标准库保存在CPU缓存中。 缓存未命中（例如，当您的代码需要从RAM复制到CPU中时）最多可能需要50条CPU指令，更不用说其他代码可能会导致另一个缓存未命中，无法将
snprintf放回缓存中。 - 消除存储要求可能会带来额外的优化。
以下描述了妨碍您的生产力的微优化。 由于您在答案中提供的信息不足，没有人回答当前的问题，可以提供任何证据，而无需做出以下假设：
- 当我们优化时，我们需要找到完整解决方案中最重要的瓶颈（您的程序旨在解决的问题） 。 这里有两种可能性：A）您想要计算要分配的字节数，以便存储包含这些数字的字符串; B）你只想计算踢的数字或数字。 稍后会详细介绍。 现在重要的是要意识到你可能正在讨论解决方案的 一部分 ，而这部分可能不是最重要的瓶颈 。
- 你正在使用的编译器，你正在使用的操作系统和你正在使用的机器（包括RAM速度，因为我们中的一些人正在引入可能受慢速内存影响而不是快速内存影响的潜在缓存未命中）可能会影响最大重大瓶颈。 有些编译器与其他编译器不同，并且会针对某些操作系统，CPU等优化某些代码片段而不是其他编译器。
您可以通过测量瓶颈来避免微观优化，即通过对系统中的每个解决方案进行分析（ “基准测试” ），假设它们甚至可以正确解决您的问题。 如果解决方案无法解决问题，那么它不是解决方案，因此不应该考虑......如果正确完成，这应该消除微优化。 有些编译器甚至提供智能的配置文件引导优化 ，通常通过重新组织缓存局部性的分支和对象来削减20-30％， 并自动完成 。
我已经涵盖了计数位数，我认为这肯定会回答你的问题，但是有些情况下你可能认为你需要计算数字而不能计算数字，并且能够消除计算数字的开销可能会产生一个非常重要的数字。在工时和机器工作时间内都需要优化。
例如，如果要计算要分配的字节数以存储包含这些数字的字符串，则不应使用任何运行时，因为预处理器宏可用于计算最大位数（或字符，包括标志），你试图保存的任何宝贵的临时存储空间都将远远超过逻辑中添加的机器代码字节数，这对我来说似乎是一笔费用。 程序员使用预处理器宏也有好处; 相同的宏可用于任何整数类型。 有关此问题的解决方案，请参阅我 对此问题的 回答 ; 毕竟，没有必要重复自己......
我想也许你可以写第一种方法
int findn(int num) { char snum[100]; return sprintf(snum, "%d", num); }
因为sprintf将返回写入的字符数，您可以将调用保存到strlen。
至于效率，我认为这取决于sprintf的实现，你可能需要找到sprintf的来源，看看它是否有效。
尝试二分搜索。 为了清楚起见，我们假设有符号的32位整数。 首先，检查x < 10000 。 接下来，根据答案，如果x < 100或x < 1000000 ，依此类推。
那是O(log n) ，其中n是数字位数。
这些函数给非正数提供了截然不同的结果（最差的是方法3），因此比较它们的时间复杂度具有可疑的价值。 我会使用能够在所有情况下提供答案的那个; 没有上下文，我们无法知道它是什么（它可能不是方法3）。
对于方法1， findn(0) == 1 ，并且findn(-n) == digits in n + 1 （由于负号）。
对于方法2， findn(0) == 0 ，并且findn(-n) == digits in n 。
对于方法3， findn(0) == INT_MIN和findn(-n) == INT_MIN也是如此。
一个class轮： for(digits = 0; num > 0; digits++) num /= 10;
我认为sprintf()将使用您的方法2来打印数字（以确定要打印的字符串的长度，然后打印字符串的每个字符），因此它本身会更慢。
3号可能涉及到ln()一些多项式近似，这将涉及更多的1个除法，所以我猜它也会更慢（ 这里是一个快速的 ln（）实现，仍然涉及浮点除法……所以WAY更慢）。
所以我的初步猜测是，方法2是要走的路。
请注意，这是解决此问题的一种非常自由的方式。 我想用每个函数测试一个很好的旧定时百万次迭代会告诉你结果。 但它太暴力了 ，不是吗？
请注意，只有方法2会为您提供真实的结果，其他方法的缺陷必须调整为正确（请参阅Aaron的答案）。 所以简单地选择方法2。
这是我的解决方案……它可以计数到100位数，或者你知道你想要它的数量。
max_digits = 100 int numdigits(int x) { for (int i = 1; i < max_digits; i++) { if (x < pow(10, i)) { return i; } } return 0; }
printf函数将返回成功打印的位数。
int digits,n=898392; digits=printf("%d",n); printf("Number of digits:%d",digits);
输出：
898392
位数：6
使用日志可能是个不错的选择……
- 如果目标计算机具有硬件支持
- 如果你确定
int可以被转换为double和back而不会丢失任何精度。
示例实施……
int num_digits(int arg) { if (arg == 0) { return 1; } arg = abs(arg); return (int)log10(arg)+1; }