宝慕林4294392
递归方法：-)int numPlaces (int n) { if (n < 0) return numPlaces ((n == INT_MIN) ? MAX_INT: -n); if (n < 10) return 1; return 1 + numPlaces (n / 10);}或迭代：int numPlaces (int n) { int r = 1; if (n < 0) n = (n == INT_MIN) ? INT_MAX: -n; while (n > 9) { n /= 10; r++; } return r;}或原始速度：int numPlaces (int n) { if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n; if (n < 10) return 1; if (n < 100) return 2; if (n < 1000) return 3; if (n < 10000) return 4; if (n < 100000) return 5; if (n < 1000000) return 6; if (n < 10000000) return 7; if (n < 100000000) return 8; if (n < 1000000000) return 9; /* 2147483647 is 2^31-1 - add more ifs as needed and adjust this final return as well. */ return 10;}修改了上面的内容，以更好地处理MININT。在任何不遵循明智的2 n二进制补码规则的怪异系统上，可能需要进一步调整。原始速度版本实际上胜过浮点版本，对其进行了以下修改：int numPlaces (int n) { if (n == 0) return 1; return floor (log10 (abs (n))) + 1;}经过一亿次迭代，我得到了以下结果：Raw speed with 0: 0 secondsRaw speed with 2^31-1: 1 secondIterative with 2^31-1: 5 secondsRecursive with 2^31-1: 6 secondsFloating point with 1: 6 secondsFloating point with 2^31-1: 7 seconds这实际上让我有些惊讶-我以为Intel芯片的FPU不错，但我想一般的FP操作仍然无法与手动优化的整数代码竞争。更新以下Stormsoul的建议：通过Stormsoul测试乘法迭代解决方案可获得4秒钟的结果，因此尽管它比除法迭代解决方案要快得多，但仍与优化的if语句解决方案不匹配。从1000个随机生成的数字中选择参数将原始速度时间缩短到2秒，因此，虽然每次都使用相同的参数似乎有些优势，但它仍然是列出的最快方法。使用-O2进行编译可以提高速度，但不能改善相对位置（我将迭代计数增加了十倍来进行检查）。任何进一步的分析都必须认真考虑CPU效率的内部工作原理（不同的优化类型，缓存的使用，分支预测，您实际拥有的CPU，房间的环境温度等等），这将妨碍我的付费工作：-)。这是一个有趣的转移，但是在某些时候，优化的投资回报变得太小了而已。我认为我们已经有了足够的解决方案来回答这个问题（毕竟，这与速度无关）。进一步更新：这将是我对此答案的最终更新，其中不包含不依赖于体系结构的明显错误。受Stormsoul勇于测量的启发，我发布了我的测试程序（根据Stormsoul自己的测试程序进行了修改）以及此处答案中显示的所有方法的一些示例图。请记住，这是在一台特定的机器上，您的行驶里程可能会因运行位置而异（这就是为什么我发布测试代码的原因）。随心所欲地处理它：#include <stdio.h>#include <stdlib.h>#include <math.h>#include <limits.h>#include <time.h>#define numof(a) (sizeof(a) / sizeof(a[0]))/* Random numbers and accuracy checks. */static int rndnum[10000];static int rt[numof(rndnum)];/* All digit counting functions here. */static int count_recur (int n) { if (n < 0) return count_recur ((n == INT_MIN) ? INT_MAX : -n); if (n < 10) return 1; return 1 + count_recur (n / 10);}static int count_diviter (int n) { int r = 1; if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n; while (n > 9) { n /= 10; r++; } return r;}static int count_multiter (int n) { unsigned int num = abs(n); unsigned int x, i; for (x=10, i=1; ; x*=10, i++) { if (num < x) return i; if (x > INT_MAX/10) return i+1; }}static int count_ifs (int n) { if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n; if (n < 10) return 1; if (n < 100) return 2; if (n < 1000) return 3; if (n < 10000) return 4; if (n < 100000) return 5; if (n < 1000000) return 6; if (n < 10000000) return 7; if (n < 100000000) return 8; if (n < 1000000000) return 9; /* 2147483647 is 2^31-1 - add more ifs as needed and adjust this final return as well. */ return 10;}static int count_revifs (int n) { if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n; if (n > 999999999) return 10; if (n > 99999999) return 9; if (n > 9999999) return 8; if (n > 999999) return 7; if (n > 99999) return 6; if (n > 9999) return 5; if (n > 999) return 4; if (n > 99) return 3; if (n > 9) return 2; return 1;}static int count_log10 (int n) { if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n; if (n == 0) return 1; return floor (log10 (n)) + 1;}static int count_bchop (int n) { int r = 1; if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n; if (n >= 100000000) { r += 8; n /= 100000000; } if (n >= 10000) { r += 4; n /= 10000; } if (n >= 100) { r += 2; n /= 100; } if (n >= 10) r++; return r;}/* Structure to control calling of functions. */typedef struct { int (*fnptr)(int); char *desc;} tFn;static tFn fn[] = { NULL, NULL, count_recur, " recursive", count_diviter, " divide-iterative", count_multiter, " multiply-iterative", count_ifs, " if-statements", count_revifs, "reverse-if-statements", count_log10, " log-10", count_bchop, " binary chop",};static clock_t clk[numof (fn)];int main (int c, char *v[]) { int i, j, k, r; int s = 1; /* Test code: printf ("%11d %d\n", INT_MIN, count_recur(INT_MIN)); for (i = -1000000000; i != 0; i /= 10) printf ("%11d %d\n", i, count_recur(i)); printf ("%11d %d\n", 0, count_recur(0)); for (i = 1; i != 1000000000; i *= 10) printf ("%11d %d\n", i, count_recur(i)); printf ("%11d %d\n", 1000000000, count_recur(1000000000)); printf ("%11d %d\n", INT_MAX, count_recur(INT_MAX)); /* */ /* Randomize and create random pool of numbers. */ srand (time (NULL)); for (j = 0; j < numof (rndnum); j++) { rndnum[j] = s * rand(); s = -s; } rndnum[0] = INT_MAX; rndnum[1] = INT_MIN; /* For testing. */ for (k = 0; k < numof (rndnum); k++) { rt[k] = (fn[1].fnptr)(rndnum[k]); } /* Test each of the functions in turn. */ clk[0] = clock(); for (i = 1; i < numof (fn); i++) { for (j = 0; j < 10000; j++) { for (k = 0; k < numof (rndnum); k++) { r = (fn[i].fnptr)(rndnum[k]); /* Test code: if (r != rt[k]) { printf ("Mismatch error [%s] %d %d %d %d\n", fn[i].desc, k, rndnum[k], rt[k], r); return 1; } /* */ } } clk[i] = clock(); } /* Print out results. */ for (i = 1; i < numof (fn); i++) { printf ("Time for %s: %10d\n", fn[i].desc, (int)(clk[i] - clk[i-1])); } return 0;}请记住，您需要确保使用正确的命令行进行编译。特别是，您可能需要明确列出数学库才能开始log10()工作。我在Debian下使用的命令行是gcc -o testprog testprog.c -lm。而且，就结果而言，这是我的环境的排行榜：优化级别0：Time for reverse-if-statements: 1704Time for if-statements: 2296Time for binary chop: 2515Time for multiply-iterative: 5141Time for divide-iterative: 7375Time for recursive: 10469Time for log-10: 26953优化级别3：Time for if-statements: 1047Time for binary chop: 1156Time for reverse-if-statements: 1500Time for multiply-iterative: 2937Time for divide-iterative: 5391Time for recursive: 8875Time for log-10: 25438