优化的itoa函数

Question

我正在考虑如何使用SSE指令实现整数(4字节，无符号)到字符串的转换。通常的例程是除以数字并将其存储在局部变量中，然后对字符串进行反转(本例中缺少反转例程)：

char *convert(unsigned int num, int base) {
    static char buff[33];  

    char *ptr;    
    ptr = &buff[sizeof(buff) - 1];    
    *ptr = '\0';

    do {
        *--ptr="0123456789abcdef"[num%base];
        num /= base;
    } while(num != 0);

    return ptr;
}

但是反转需要额外的时间。除了SSE指令之外，是否还有其他算法可以用来并行化函数？

Answer 1

优化代码的第一步是摆脱任意的基础支持。这是因为除以常量几乎肯定是乘法，但除以base是除法，而且因为'0'+n比"0123456789abcdef"[n]快(前者不涉及内存)。

如果你需要更进一步，你可以为你关心的基数中的每个字节制作查找表(例如10)，然后向量相加每个字节的结果(例如十进制)。如下所示：

00 02 00 80 (input)

 0000000000 (place3[0x00])
+0000131072 (place2[0x02])
+0000000000 (place1[0x00])
+0000000128 (place0[0x80])
 ==========
 0000131200 (result)

Answer 2

This post比较了几种整数到字符串转换的方法，也就是itoa。据报道，最快的方法是来自the {fmt} library的fmt::format_int，它比sprintf/std::stringstream快5-18倍，比简单的ltoa/itoa实现快约4倍(当然，实际数字可能会因平台而异)。

与大多数其他方法不同，fmt::format_int只传递一次数字。它还使用Alexandrescu的talk Fastware中的想法最小化整数除法的数量。这个实现可以在here上找到。

当然，如果C++是一个选项，并且您不受itoa的API的限制，则可以这样做。

免责声明:我是这个方法和fmt library的作者。

Answer 3

http://sourceforge.net/projects/itoa/

它使用一个包含所有4位整数的大型静态常量数组，并将其用于32位或64位到字符串的转换。

可移植，不需要特定的指令集。

我能找到的唯一更快的版本是汇编代码，并且被限制为32位。