计算位数 - 哪种方法最有效？

Question

有一种以上的解决方案可以找到给定数字中的数字位数.

例如:

方法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怎么样？如何找到库函数的运行时复杂性？

Answer 1

以下更有效:

int findn(int num)
{
   if ( num < 10 )
      return 1;
   if ( num < 100 )
      return 2;
   //continue until max int
}

您可以通过二进制搜索进一步优化这一点,但这样做太过分了.

Answer 2

目前看来,对于负数而言,接受且最高度认可的答案(仍然)是不正确的.如果回答者花时间测试它并发现它已被打破为负数,他可能会浪费更多的时间而不是通过简单地使用机器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%,并自动完成.

我已经涵盖了计数数字,我认为这肯定会回答你的问题,但是有些情况下你可能认为你需要计算数字而不能计算数字,并且能够消除计算数字的开销可能会产生很大的数字.在工时和机器工作时间内都需要优化.

例如,如果要计算要分配的字节数以存储包含这些数字的字符串,则不应使用任何运行时,因为预处理器宏可用于计算最大位数(或字符,包括标志),你试图保存的任何宝贵的临时存储字节数都将远远超过逻辑中添加的机器代码字节数,这对我来说似乎是一笔费用.程序员使用预处理器宏也有好处; 相同的宏可用于任何整数类型.见我的回答对这个问题的一个解决这个问题 ; 毕竟,没有必要重复自己......

Answer 3

GCC/Clang __builtin_clz()或Microsoft Visual C _BitScanReverse()内部函数在许多机器上编译为单个机器指令.您可以将其用作O(1)解决方案的基础.这是一个32位的实现:

#include <limits.h>
#include <stdint.h>

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

Answer 4

我想也许你可以写第一种方法

int findn(int num)
{
    char snum[100];    
    return  sprintf(snum, "%d", num);
}

因为sprintf将返回写入的字符数,您可以将调用保存到strlen.

至于效率,我认为这取决于sprintf的实现,你可能需要找到sprintf的来源,看看它是否有效.