例如,
n = 3432, result 4 n = 45, result 2 n = 33215, result 5 n = -357, result 3
我想我可以把它变成一个字符串然后得到字符串的长度,但这看起来很复杂和黑客.
递归方法:-)
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 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操作仍然无法与手工优化的整数代码竞争.
更新以下stormsoul的建议:
通过stormsoul测试乘法迭代解决方案得到4秒的结果,虽然它比除法迭代解决方案快得多,但它仍然与优化的if语句解决方案不匹配.
从1000个随机生成的数字池中选择参数会将原始速度时间推迟到2秒,因此看起来每次使用相同的参数可能有一些优势,它仍然是列出的最快方法.
使用-O2进行编译可以提高速度但不会提高相对位置(我将迭代次数增加了十倍来检查).
任何进一步的分析都必须认真对待CPU效率的内部工作(不同类型的优化,缓存的使用,分支预测,你实际拥有的CPU,房间里的环境温度等),这将是妨碍我的有偿工作:-).这是一个有趣的转移,但在某些时候,优化投资的回报变得太小而无关紧要.我认为我们有足够的解决方案来回答这个问题(毕竟,这不是关于速度).
进一步更新:
这将是我对此答案的最终更新,除非明显不依赖于体系结构的错误.受到stormsoul勇敢测量的启发,我发布了我的测试程序(根据stormsoul自己的测试程序修改)以及这里答案中显示的所有方法的一些示例数字.请记住,这是在特定的机器上,您的里程可能会因您运行它的位置而有所不同(这就是我发布测试代码的原因).
随心所欲:
#include#include #include #include #include #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: 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
floor (log10 (abs (x))) + 1
http://en.wikipedia.org/wiki/Logarithm
最短的答案: snprintf(0,0,"%+d",n)-1
二进制搜索伪算法得到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;
在循环中除以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
这避免了任何计算上昂贵的功能,例如日志甚至乘法或除法.虽然它不够优雅,但可以通过将其封装到一个函数中来隐藏它.它不复杂或难以维护,因此我不会因编码不良而忽略这种方法; 我觉得这样做会把洗澡水扔掉.
使用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的事实.
更新:
根据建议,这里有count_bsr和一个稍微快一点的64位count_bsr_mod例程的时间,与二进制搜索和二进制斩波算法相比,使用非常好的paxdiablo测试程序进行修改以生成具有随机符号分布的集合.测试是使用gcc 4.9.2使用"-O3 -falign-functions = 16 -falign-jumps = 16 -march = corei7-avx"选项构建的,并在一个静止的Sandy Bridge系统上执行,并且关闭了turbo和sleep状态.
Time for bsr mod: 270000 Time for bsr: 340000 Time for binary chop: 800000 Time for binary search: 770000 Time for binary search mod: 470000
测试来源,
#include#include #include #include #include #include #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 Hacks:
以明显的方式查找整数的整数对数10
请注意其中的比较顺序.
京公网安备 11010802040832号 | 京ICP备19059560号-6 