快速整数转十进制转换

Question

给定一个（无符号）整数，将其转换为包含它的十进制表示的字符串，通常最快的方法是什么？

直接重复地除以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';
}

- fuz

---

如果给定一个（无符号）整数，通常最快的将其转换为整数的方法是什么？您是指如果已经有了一个字符串吗？因为将整数转换为整数的最快方法就是什么也不用做 :) - Justin

@FUZxxl 对不起，我经常会无意中跳到 C 标签里。 - Seth Carnegie

@Seth 没问题。我只是有点不喜欢“只需使用X，我不关心也不知道它是如何工作的”的说法。 - fuz

@FUZxxl 这取决于你所说的“快”的含义。如果你真的想要完成某件事情，使用内置函数是最快的。所以我想以这种方式回答它（尽管这不是我当时知道的C++）。没有恶意。 - Seth Carnegie

紧密相关：这个问题的C++版本 - Ben Voigt

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

- Ben Voigt

---

很有趣。我打算写一个程序来比较这种方法和我的方法。 - fuz

@FUZxxl：我建议你点击进入那个其他问题。已经有很多代码，包括性能数据和需要进行自己测试的基准代码。 - Ben Voigt

Answer 2

我相信使用常数进行整数除法与进行乘法的速度一样快，因为编译器会针对常数除数将整数除法优化为整数乘法。这是大多数优化编译器执行的重量级数学技巧。

- usr

---

整数乘法仍然相当缓慢，因为它是一种非流水线、微码操作，这意味着整个乱序执行（OOO）流水线在执行时会完全停止。有关x86的内容，请参阅《Intel® 64和IA-32架构优化参考手册》；从我的经验来看，PowerPC上的情况甚至更糟。 - Crashworks

@Crashworks，我没有这方面的经验，但我尊重你的意见。这真是令人惊讶。那么像Core i7这样一流的CPU呢？它们一定要使用流水线乘法吗？ - usr

@usr 我不熟悉这个优化。你有参考资料吗？我唯一能想到的是使用模反元素，但那只适用于奇数。 - vhallac

@BenVoigt 这不是用于模乘吗？ - vhallac

这篇博客系列非常出色，我在几天前阅读了它。 - usr

@vhallac 是的，所有计算机整数运算都是模运算（在2^32或2^64上）。一开始我不相信这个答案，直到我看了我的编译器的输出，它确实发出了一个乘法逆元。usr：我相信那个指南是针对现代i7的。整数乘法很难适应流水线，因为它有很多门延迟（http://bit.ly/JQRyeY）。此外，许多CPU将其实现为一个部分积加法器单元上的迭代算法，这意味着它是微码化的，也不是恒定数量的步骤。 - Crashworks

Answer 3

MS版本的printf函数采用了“天真”的方式（在设置了一堆基于可选标志的变量之后）：

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

- AShelly

Answer 4

通常最快的方法是索引到足够大的字符串指针数组中。一个数组查找，一个指针解引用。但这会占用大量内存...这就是工程权衡的本质。多快才算够快呢？

- Jens

---

没有所谓的“足够快”。无论哪种表现最佳，都是“足够快”的。 - fuz

是的，存在“足够快”的情况，因为通常最佳性能是由于过高的资源需求而无法达到的。我的回答就是最好的例子。你有足够的内存来存储2**64个指针和相关字符串吗？可能没有。但我非常自信这样做会获得最佳性能。 - Jens

不错的反驳。在几乎所有的机器上，如果没有缓存，内存访问速度都非常慢。因此，尽量减少内存访问次数可能是一个优势。 - fuz