我如何确定C中的整数位数?

例如,

n = 3432, result 4 n = 45, result 2 n = 33215, result 5 n = -357, result 3 

我想我可以把它变成一个string,然后得到string的长度,但似乎令人费解和hack-y。

 floor (log10 (abs (x))) + 1 

http://en.wikipedia.org/wiki/Logarithm

recursion方法:-)

 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。 在任何不符合整数规律的奇怪系统中,它们可能需要进一步的调整。

原始速度版本实际上超过了浮点版本,修改如下:

 int numPlaces (int n) { if (n == 0) return 1; return floor (log10 (abs (n))) + 1; } 

有了一亿次的迭代,我得到了以下结果:

 Raw speed with 0: 0 seconds Raw speed with 2^31-1: 1 second Iterative with 2^31-1: 5 seconds Recursive with 2^31-1: 6 seconds Floating point with 1: 6 seconds Floating point with 2^31-1: 7 seconds 

这实际上让我感到惊讶 – 我认为英特尔芯片有一个体面的FPU,但我认为一般的FP操作仍然不能与手工优化的整数代码竞争。

更新以下暴风雨的build议:

用stormsoultesting乘法迭代解决scheme的结果是4秒,虽然比迭代解决scheme快得多,但它仍然不符合优化的if语句解决scheme。

从一个由1000个随机生成的数字组成的池中select参数将原始速度时间推到了2秒,虽然看起来每次都有相同的参数可能有一些优势,但它仍然是列出的最快的方法。

用-O2编译提高了速度,但不是相对位置(我把迭代次数增加了十倍来检查这个)。

任何进一步的分析都必须认真考虑CPU效率的内部工作(不同types的优化,高速caching的使用,分支预测,你实际拥有的CPU,房间里的环境温度等等)阻碍我付费的工作:-)。 这是一个有趣的分stream,但在某种程度上,优化的投资回报变得太小而无关紧要。 我认为我们有足够的解决scheme来回答这个问题(毕竟,这不是速度问题)。

进一步更新:

这将是我对这个答案的最终更新,除了不依赖于架构的明显的错误。 受到风暴灵魂勇于测量的启发,我发布了我的testing程序(根据stormsoul自己的testing程序进行了修改),并附上了答案中显示的所有方法的一些示例数字。 请记住,这是在一台特定的机器 ,你的里程可能会有所不同,这取决于你在哪里运行(这就是为什么我发布的testing代码)。

按照你的意愿去做:

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

请记住,您需要确保使用正确的命令行进行编译。 尤其是,您可能需要明确列出math库才能使log10()工作。 我在Debian下使用的命令行是gcc -o testprog testprog.c -lm

而就结果而言,这里是我所处环境的领导者:

优化级别0:

 Time for reverse-if-statements: 1704 Time for if-statements: 2296 Time for binary chop: 2515 Time for multiply-iterative: 5141 Time for divide-iterative: 7375 Time for recursive: 10469 Time for log-10: 26953 

优化级别3:

 Time for if-statements: 1047 Time for binary chop: 1156 Time for reverse-if-statements: 1500 Time for multiply-iterative: 2937 Time for divide-iterative: 5391 Time for recursive: 8875 Time for log-10: 25438 

二进制search伪algorithm在v中得到r的数字

 if (v < 0 ) v=-v; r=1; if (v >= 100000000) { r+=8; v/=100000000; } if (v >= 10000) { r+=4; v/=10000; } if (v >= 100) { r+=2; v/=100; } if( v>=10) { r+=1; } return r; 

最短的答案是: snprintf(0,0,"%+d",n)-1

一个循环中除以10,直到结果为零。 迭代次数将对应于小数位数。

假设你期望在零值中得到0位:

 int countDigits( int value ) { int result = 0; while( value != 0 ) { value /= 10; result++; } return result; } 

你可以这样做: floor (log10 (abs (x))) + 1或者如果你想节省周期,你可以做比较

 if(x<10) return 1; if(x<100) return 2; if(x<1000) return 3; etc etc 

这避免了任何计算上昂贵的function,如日志甚至乘法或除法。 虽然它不雅,但可以通过将其封装到函数中来隐藏。 维护起来并不复杂或难度很大,所以我不会因为编码实践不好而忽略这种方法。 我觉得这样做会把婴儿扔出去。

使用x86汇编和查找表的恒定成本版本:

 int count_bsr(int i) { struct { int max; int count; } static digits[32] = { { 9, 1 }, { 9, 1 }, { 9, 1 }, { 9, 1 }, { 99, 2 }, { 99, 2 }, { 99, 2 }, { 999, 3 }, { 999, 3 }, { 999, 3 }, { 9999, 4 }, { 9999, 4 }, { 9999, 4 }, { 9999, 4 }, { 99999, 5 }, { 99999, 5 }, { 99999, 5 }, { 999999, 6 }, { 999999, 6 }, { 999999, 6 }, { 9999999, 7 }, { 9999999, 7 }, { 9999999, 7 }, { 9999999, 7 }, { 99999999, 8 }, { 99999999, 8 }, { 99999999, 8 }, { 999999999, 9 }, { 999999999, 9 }, { 999999999, 9 }, { INT_MAX, 10 }, { INT_MAX, 10 } }; register const int z = 0; register unsigned log2; if (i < 0) i = -i; __asm__ __volatile__ ( "bsr %1, %0;" \ "cmovz %2, %0;"\ : "=r" (log2) \ : "rm" (i), "r"(z)); return digits[log2].count + ( i > digits[log2].max ); } 

另一个,用一个较小的查找表和从这里采取的log10近似值。

 int count_bsr2( int i ) { static const unsigned limits[] = {0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000}; register const int z = 0; register int l, log2; if (i < 0) i = -i; __asm__ __volatile__ ( "bsr %1, %0;" \ "cmovz %2, %0;"\ : "=r" (log2) \ : "rm" (i), "r"(z)); l = (log2 + 1) * 1233 >> 12; return (l + ((unsigned)i >= limits[l])); } 

这两个都利用了x86-INT_MIN等于INT_MIN的事实。

更新:

根据build议,这里是count_bsr的计时和稍微快一点的64位count_bsr_mod例程与二进制search和二进制chopalgorithm比较,使用非常好的paxdiablo的testing程序修改以生成具有随机符号分布的集合。 testing是用gcc 4.9.2使用“-O3 -falign-functions = 16 -falign-jumps = 16 -march = corei7-avx”选项来构build的,并且在closuresturbo和睡眠状态的其他静态的Sandy Bridge系统上执行。

时间为BSR MOD:270000  
时间为bsr:340000  
二进制砍时间:800000  
二进制search时间:770000  
二进制search的时间mod:470000  

testing来源,

 #include <stdint.h> #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_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; } static int count_bsearch(int i) { if (i < 0) { if (i == INT_MIN) return 11; // special case for -2^31 because 2^31 can't fit in a two's complement 32-bit integer i = -i; } if (i < 100000) { if (i < 1000) { if (i < 10) return 1; else if (i < 100) return 2; else return 3; } else { if (i < 10000) return 4; else return 5; } } else { if (i < 10000000) { if (i < 1000000) return 6; else return 7; } else { if (i < 100000000) return 8; else if (i < 1000000000) return 9; else return 10; } } } // Integer log base 10, modified binary search. static int count_bsearch_mod(int i) { unsigned x = (i >= 0) ? i : -i; if (x > 99) if (x > 999999) if (x > 99999999) return 9 + (x > 999999999); else return 7 + (x > 9999999); else if (x > 9999) return 5 + (x > 99999); else return 3 + (x > 999); else return 1 + (x > 9); } static int count_bsr_mod(int i) { struct { int m_count; int m_threshold; } static digits[32] = { { 1, 9 }, { 1, 9 }, { 1, 9 }, { 1, 9 }, { 2, 99 }, { 2, 99 }, { 2, 99 }, { 3, 999 }, { 3, 999 }, { 3, 999 }, { 4, 9999 }, { 4, 9999 }, { 4, 9999 }, { 4, 9999 }, { 5, 99999 }, { 5, 99999 }, { 5, 99999 }, { 6, 999999 }, { 6, 999999 }, { 6, 999999 }, { 7, 9999999 }, { 7, 9999999 }, { 7, 9999999 }, { 7, 9999999 }, { 8, 99999999 }, { 8, 99999999 }, { 8, 99999999 }, { 9, 999999999 }, { 9, 999999999 }, { 9, 999999999 }, { 10, INT_MAX }, { 10, INT_MAX } }; __asm__ __volatile__ ( "cdq \n\t" "xorl %%edx, %0 \n\t" "subl %%edx, %0 \n\t" "movl %0, %%edx \n\t" "bsrl %0, %0 \n\t" "shlq $32, %%rdx \n\t" "movq %P1(,%q0,8), %q0 \n\t" "cmpq %q0, %%rdx \n\t" "setg %%dl \n\t" "addl %%edx, %0 \n\t" : "+a"(i) : "i"(digits) : "rdx", "cc" ); return i; } static int count_bsr(int i) { struct { int max; int count; } static digits[32] = { { 9, 1 }, { 9, 1 }, { 9, 1 }, { 9, 1 }, { 99, 2 }, { 99, 2 }, { 99, 2 }, { 999, 3 }, { 999, 3 }, { 999, 3 }, { 9999, 4 }, { 9999, 4 }, { 9999, 4 }, { 9999, 4 }, { 99999, 5 }, { 99999, 5 }, { 99999, 5 }, { 999999, 6 }, { 999999, 6 }, { 999999, 6 }, { 9999999, 7 }, { 9999999, 7 }, { 9999999, 7 }, { 9999999, 7 }, { 99999999, 8 }, { 99999999, 8 }, { 99999999, 8 }, { 999999999, 9 }, { 999999999, 9 }, { 999999999, 9 }, { INT_MAX, 10 }, { INT_MAX, 10 } }; register const int z = 0; register unsigned log2; if (i < 0) i = -i; __asm__ __volatile__ ( "bsr %1, %0;" \ "cmovz %2, %0;"\ : "=r" (log2) \ : "rm" (i), "r"(z)); return digits[log2].count + ( i > digits[log2].max ); } /* Structure to control calling of functions. */ typedef struct { int (*fnptr)(int); const char *desc; } tFn; static tFn fn[] = { { NULL, NULL }, { count_bsr_mod, " bsr mod" }, { count_bsr, " bsr" }, { count_bchop, " binary chop" }, { count_bsearch, " binary search" }, { count_bsearch_mod," binary search mod"} }; 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_bsearch(INT_MIN)); //for (i = -1000000000; i != 0; i /= 10) for (i = -999999999; i != 0; i /= 10) printf ("%11d %d\n", i, count_bsearch(i)); printf ("%11d %d\n", 0, count_bsearch(0)); for (i = 1; i != 1000000000; i *= 10) printf ("%11d %d\n", i, count_bsearch(i)); printf ("%11d %d\n", 1000000000, count_bsearch(1000000000)); printf ("%11d %d\n", INT_MAX, count_bsearch(INT_MAX)); return 0; /* */ /* Randomize and create random pool of numbers. */ int p, n; p = n = 0; srand (time (NULL)); for (j = 0; j < numof (rndnum); j++) { rndnum[j] = ((rand() & 2) - 1) * rand(); } 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; } 

从Bit Twiddling黑客:

以一个明显的方式find一个整型数的整数

请注意其中的比较顺序。

这是一个展开的二进制search,没有任何除法或乘法。 根据给定的数字的分布情况,它可能会或可能不会打败其他展开的if语句,但应该总是击败那些使用循环和multiplication / division / log10的语句。

在我的机器上,随机数的均匀分布在我的机器上平均为paxdiablo的count_bchop()的执行时间的79%,count_ifs()的88%和count_revifs()的97%。

用指数分布(一个有n个数字的数字的概率等于它有m个数字的概率,其中mn ),count_ifs()和count_revifs()都击败了我的函数。 我不知道为什么在这一点上。

 int count_bsearch(int i) { if (i < 0) { if (i == INT_MIN) return 11; // special case for -2^31 because 2^31 can't fit in a two's complement 32-bit integer i = -i; } if (i < 100000) { if (i < 1000) { if (i < 10) return 1; else if (i < 100) return 2; else return 3; } else { if (i < 10000) return 4; else return 5; } } else { if (i < 10000000) { if (i < 1000000) return 6; else return 7; } else { if (i < 100000000) return 8; else if (i < 1000000000) return 9; else return 10; } } } 

我在谷歌search中偶然发现了这个: http : //www.hackersdelight.org/hdcodetxt/ilog.c.txt

快速的基准清楚地显示了二进制search方法获胜。 lakshmanaraj的代码是相当不错的, Alexander Korobka的速度快了30%, Deadcode的速度还是快了一点点(〜10%),但是我发现上面的链接进一步提高了10%。

 // Integer log base 10, modified binary search. int ilog10c(unsigned x) { if (x > 99) if (x < 1000000) if (x < 10000) return 3 + ((int)(x - 1000) >> 31); // return 3 - ((x - 1000) >> 31); // Alternative. // return 2 + ((999 - x) >> 31); // Alternative. // return 2 + ((x + 2147482648) >> 31); // Alternative. else return 5 + ((int)(x - 100000) >> 31); else if (x < 100000000) return 7 + ((int)(x - 10000000) >> 31); else return 9 + ((int)((x-1000000000)&~x) >> 31); // return 8 + (((x + 1147483648) | x) >> 31); // Alternative. else if (x > 9) return 1; else return ((int)(x - 1) >> 31); // return ((int)(x - 1) >> 31) | ((unsigned)(9 - x) >> 31); // Alt. // return (x > 9) + (x > 0) - 1; // Alt. } 

注意这是日志10,而不是数字的位数,所以digits = ilog10c(x)+1

不支持底片,但用-很容易修复。

  int n = 437788; int N = 1; while (n /= 10) N++; 
 if (x == MININT) return 10; // abs(MININT) is not defined x = abs (x); if (x<10) return 1; if (x<100) return 2; if (x<1000) return 3; if (x<10000) return 4; if (x<100000) return 5; if (x<1000000) return 6; if (x<10000000) return 7; if (x<100000000) return 8; if (x<1000000000) return 9; return 10; //max len for 32-bit integers 

非常不雅。 但比所有其他解决scheme更快。 整数部门和FP日志是昂贵的。 如果性能不是问题,log10解决scheme是我的最爱。

只需稍微调整一下C语言:

 floor( log10( abs( (number)?number:1 ) ) + 1 ); 

不要使用楼层(log10(…))。 这些是浮点函数,而且是缓慢的函数。 我相信最快的方法就是这个function:

 int ilog10(int num) { unsigned int num = abs(num); 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; } } 

请注意,由于分支预测失误,某些人build议的二进制search版本可能会变慢。

编辑:

我做了一些testing,并得到了一些非常有趣的结果。 我将函数和Paxtesting的所有函数一起计时,以及由lakshmanaraj给出的二进制search函数。 testing由以下代码片段完成:

 start = clock(); for(int i=0; i<10000; i++) for(int j=0; j<10000; j++) tested_func(numbers[j]); end = clock(); tested_func_times[pass] = end-start; 

其中numbers []数组在整型范围内包含随机生成的数字(禁止MIN_INT)。 对同一数字[]数组上的每个testing函数重复testing。 整个testing进行了10次,结果平均在所有的通过。 代码是用-O3优化级别的GCC 4.3.2编译的。

结果如下:

 floating-point log10: 10340ms recursive divide: 3391ms iterative divide: 2289ms iterative multiplication: 1071ms unrolled tests: 859ms binary search: 539ms 

我必须说我真的很惊讶。 二进制search比我想象的要好得多。 我检查了GCC如何编译这个代码到ASM。 O_O。 现在这是令人印象深刻的。 它得到了比我想象的更好的优化,避免了大多数分支以非常聪明的方式。 难怪它是快速的。

you can find number of digits in a number by using this formaula ceil (log10 (abs (x))) where ceil returns a integer number just greater than number

I guess, the simplest way would be:

  int digits = 0; if (number < 0) digits = 1; while (number) { number /= 10; digits++; } 

digits gives the answer.

A simple way to find the length (ie number of digits) of signed integer is this:

 while ( abs(n) > 9 ) { num /= 10; ++len; } 

Where n is the integer you want to find the length of and where len is equal to the number of digits in the integer. This works for both values of n (negative or positive).

The call on abs() is optional, if you are only working with positive integers.

 void main() { int a,i; printf("Enter the number :"); scanf("%d",&a); while(a>0) { a=a/10; i++; } getch(); }