快速整数到十进制转换
给定（无符号）整数，将它转换为包含十进制表示的字符串的最常用方法是什么？
这种天真的做法是重复除以10，直到你达到零。 我不喜欢这种方法，因为它
- 使用整数除法，它在某些集成平台上既慢又不可用
- 要求程序员在之后翻转字符串。 这使所需的内存操作数量翻倍。
我想到了以下方法将整数转换为十进制基数。 这是一个好主意吗？ 这是如何在printf这样的printf常见实现中完成的？
#include const static uint64_t i64_tab[20] = { 1u, 10u, 100u, 1000u, 10000u, 100000u, /* 10^ 5 */ 1000000u, 10000000u, 100000000u, 1000000000u, 10000000000u, /* 10^10 */ 100000000000u, 1000000000000u, 10000000000000u, 100000000000000u, 1000000000000000u, /* 10^15 */ 10000000000000000u, 100000000000000000u, 1000000000000000000u, 10000000000000000000u /* 10^19 */ }; void uint64_to_string(char *out, uint64_t in) { int i; uint64_t tenpow; char accum; for (i = 19;i > 0;i--) { if (in >= i64_tab[i]) break; } do { tenpow = i64_tab[i]; accum = '0'; while (in >= tenpow) { in -= tenpow; accum++; } *out++ = accum; } while (i --> 0); *out = '\0'; } const static uint32_t i32_tab[10] = { 1u, 10u, 100u, 1000u, 10000u, 100000u, /* 10^ 5 */ 1000000u, 10000000u, 100000000u, 1000000000u, /* 10^9 */ }; void uint32_to_string(char *out, uint32_t in) { int i; uint32_t tenpow; char accum; for (i = 9;i > 0;i--) if (in >= i32_tab[i]) break; do { tenpow = i32_tab[i]; accum = '0'; while (in >= tenpow) { in -= tenpow; accum++; } *out++ = accum; } while (i --> 0); *out = '\0'; }
除最简单（例如8位）微控制器之外的所有微控制器的最快方法是使用除法，但通过一次生成多个数字来减少除法数。
您将在此处找到我的问题的答案中非常高度优化的代码。 在C中使用它应该是一个简单的编辑来消除std::string – 在实际转换中没有使用C ++特性。 核心是
while(val>=100) { int pos = val % 100; val /= 100; *(short*)(c-1)=*(short*)(digit_pairs+2*pos); // or use memcpy c-=2; } while(val>0) { *c--='0' + (val % 10); val /= 10; }
我还为8位微处理器提供了一个优化的无分区代码，类似于问题代码中显示的思想，但没有循环。 它最终得到了很多像这样的代码：
if (val >= 80) { ch |= '8'; val -= 80; } else if (val >= 40) { ch |= '4'; val -= 40; } if (val >= 20) { ch |= '2'; val -= 20; } if (val >= 10) { ch |= '1'; val -= 10; }
我认为通过常数进行整数除法与进行乘法一样快，因为编译器将整数除法优化为常数除数的整数乘法。 这是大多数优化编译器执行的重型数学技巧。
通常最快的方法是索引到一个足够大的字符串指针数组。 一个数组查找，一个指针解除引用。 尽管如此……内存使用量很大……这就是工程权衡的本质。 速度有多快？
printf的MS版本以“天真”的方式（在根据可选标志设置一堆变量之后）：
while (precision-- > 0 || number != 0) { digit = (int)(number % radix) + '0'; number /= radix; /* reduce number */ if (digit > '9') { /* a hex digit, make it a letter */ digit += hexadd; } *text.sz-- = (char)digit; /* store the digit */ }