快速整数十进制转换(Fast integer to decimal conversion)

给定一个（无符号）整数，究竟是将其转换成一个包含其十进制表示的字符串一般最快的方法？

这样做，反复10分，直到你达到零的用简单的方式。 我不喜欢这种做法，因为它

• 使用整数除法，这是既慢又不适用于某些综合平台
• 需要程序员之后翻转的字符串。 这需要加倍内存操作的数量。

我想下面的方法整数转换为十进制基地。 这是一个好主意吗？ 这是如何在类似的功能常见的实现做了printf ？

#include <stdint.h>

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

Answer 1:

在微控制器所有，但最简单的（例如，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;
    }

Answer 2:

我相信，通过恒定整数除法是一样快，因为编译器优化整数除法整数乘法恒定除数做乘法。 这是最优化的编译器进行了重载的数学技巧。

Answer 3:

一般最快的方法是索引指针一个足够大的数组的字符串。 一个阵列查找，一个指针引用。 这是对内存的使用沉重，但...这就是工程折衷的性质。 如何快是够快？

Answer 4:

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

文章来源: Fast integer to decimal conversion