为什么x86-64（或其他架构）不实现除以10？

Question

我熟悉编译器用常量（例如

x/10

）替换除法和取模，并乘以幻数

(x * 0xcccccccd) >> (32 + 3)

。 编译器示例在这里。

        movl    $1717986919, %edx
        addl    $12, %esp
        movl    %ecx, %eax
        imull   %edx
        movl    %ecx, %eax
        sarl    $31, %eax
        sarl    $2, %edx
        subl    %eax, %edx
        leal    (%edx,%edx,4), %eax
        addl    %eax, %eax
        subl    %eax, %ecx

同时，我有点惊讶没有一些 x86-64 指令可以做到这一点：

edx <= eax % 10
eax <= eax / 10

对于 int 到 string 或任何需要十进制基数的东西来说，除以 10 似乎是一个相当常见的操作。 x86-64 还因提供一些利基指令而闻名，其中许多指令结合了一个或多个常见指令（例如，融合乘加扩展）。看起来芯片可能比编译器做得稍好一些？

我希望找到一个答案，其中包含一些文档或历史（而不仅仅是猜测），如果存在的话。尽管我知道可能很难找到解释为什么架构开发人员没有做了一些事情。

相关：

• 为什么GCC在实现整数除法时使用乘以奇怪的数字？
• 实模式支持BCD运算
• 回顾计算：是否有任何 CPU 有乘以或除以 10 的特殊指令？

Answer 1

自 20 世纪 90 年代中期以来，即 x86-64 工作开始的几年前，众所周知，整数除以常量不需要除法，但可以通过整数乘法来计算乘法:

Torbjörn Granlund 和 Peter L. Montgomery，“使用乘法除以不变整数。” ACM SIGPLAN 1994 年编程语言设计和实现会议记录。 1994 年 6 月，第 61-72 页

有 are 应用程序大量使用整数到 ASCII 转换，这与应用程序性能相关。我似乎记得早期的网络浏览器就属于这些应用程序，以及商业处理中使用的各种软件。但这样的转换甚至不需要许多除以常数的运算。可以将整数转换为二进制定点表示一次，然后使用十的乘法将十进制数字一位一位地取出。

这种通用基数转换技术太老了，我什至没有参考资料。在电子计算机出现之前，它可能是手动使用的。这也是 x87 FPU 中的

FBSTP

指令在内部工作的方式，或者至少这是我为 Athlon 处理器的 FPU 实现它的方式。现在，

FBSTP

很少使用，而且微码ROM是非常昂贵的资源，所以我针对空间而不是速度优化了微码。

这种 32 位整数转换方法在 ISO-C99 中的实现可能类似于下面的代码。

umul32_wide()

函数是 x86

MUL

指令的 C 级等效项。为了使这段代码运行得更快，需要一个快速的整数乘法器。 一般快速整数乘法在许多环境中都很重要，x86-64 设计团队当然知道这一点。

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

void umul32_wide (uint32_t a, uint32_t b, uint32_t *hi, uint32_t *lo)
{
    uint64_t prod = (uint64_t)a * b;
    *hi = (uint32_t)(prod >> 32);
    *lo = (uint32_t)prod;
}

void cvt_uint32 (uint32_t x, char *out)
{
    uint32_t hi, lo, num, digcnt;
    uint32_t dig;

    /* find first digit, in [0,4], separately */
    umul32_wide (x, 0x89705f41, &hi, &lo); // 2**61 / 10**9 rounded
    num = hi + (lo >> 31);
    dig = num >> 29;
    x = x - 1000000000 * dig;
    *out++ = dig | '0';

    /* convert number in [0, 999999999] to 4:28 fixed-point */
    umul32_wide (x, 0xabcc7712, &hi, &lo); // (2**28 / 10**8) * 2**30 rounded up
    num = (hi << 2) + (lo >> 30) + 1;

    /* pull out decimal digits one at a time */
    dig = (num >> 28) | '0';
    num = num & 0x0fffffff;
    digcnt = 8;
    do {
        *out++ = dig;
        num = num * 10;
        dig = (num >> 28) | '0';
        num = num & 0x0fffffff;
        digcnt--;
    } while (digcnt);
    *out = dig;
}

int main (void)
{
    char res [17] = {0};
    char ref [17] = {0};

    printf ("Testing uint32 exhaustively\n");
    unsigned int x;
    x = 0;
    do {
        cvt_uint32 (x, res);
        sprintf (ref, "%010u", x);
        if (memcmp (res, ref, 8) != 0) {
            printf ("error: t=%08u  res=%s  ref=%s\n", x, res, ref);
            return EXIT_FAILURE;
        }
        x++;
    } while (x);
    return EXIT_SUCCESS;
}

有人可能会问：但是这段代码中的乘以 10 呢？不需要。人们可以完全展开循环，将其替换为乘以 5，并以每步一位动态调整定点表示。在 x86-64 之前，高性能乘 5 功能已经以

LEA

指令的形式存在。

另一个观察结果是上面显示的代码具有串行性质，ILP 有限。通过使用常数除法（10¹⁰，10⁵）将整数划分为块（可能是递归的）来创建块，可以轻松解决这个问题。如今，正如评论中指出的那样，甚至有更聪明的方法。