GCC/ARM上的快速除法

Question

据我所知，大多数编译器通过乘法和右移位来进行快速除法。例如，如果您查看这个SO线程，它说当您要求Microsoft编译器执行除以10的操作时，它将通过0x1999999A(即2^32/10)将被除数与乘积相乘，然后将结果除以2^32(使用32次右移)。

（编辑注：直到最近之前，该链接的答案是错误的。编译器不会这样做，因为对于所有输入来说都不是准确的。编译器确实使用乘法和移位，但是有更复杂的方式来确定神奇常数和移位计数：为什么GCC在实现整数除法时使用奇怪的数字进行乘法？）

---

到目前为止一切顺利。

然而，当我在ARM上使用GCC测试同样的除以10时，编译器做了一些略微不同的事情。首先，它将被除数与0x66666667 (2^34/10)相乘，然后将结果除以2^34。到目前为止，这与Microsoft相同，只是使用更高的乘数。之后，它从结果中减去了(被除数/2^31)。

我的问题：为什么ARM版本会有额外的减法？您能否给出一个数字示例，在没有那个减法的情况下，结果将是错误的？

如果您想检查生成的代码，请参阅以下内容（带有我的注释）：

        ldr     r2, [r7, #4] @--this loads the dividend from memory into r2
        movw    r3, #:lower16:1717986919 @--moves the lower 16 bits of the constant 
        movt    r3, #:upper16:1717986919 @--moves the upper 16 bits of the constant
        smull   r1, r3, r3, r2 @--multiply long, put lower 32 bits in r1, higher 32 in r3
        asr     r1, r3, #2 @--r3>>2, then store in r1 (effectively >>34, since r3 was higher 32 bits of multiplication)
        asr     r3, r2, #31 @--dividend>>31, then store in r3
        rsb     r3, r3, r1 @--r1 - r3, store in r3
        str     r3, [r7, #0] @--this stores the result in memory (from r3) 

- Daniel Scocco

---

针对负数，整数除法将截断结果，并且只有乘法和位移会产生负数 x 的 x/10 - 1 结果。（当然，假设使用算术右移。） - Daniel Fischer

我可以看出，如果我使用乘法/移位方法进行 -99 / 10 计算，结果会得到 -10。但如果我从中减去 1，则会得到 -11，而我想要的是 -9，不是吗？ - Daniel Scocco

你需要减去“-1”，也就是加上1。 - Daniel Fischer

Answer 1

然后，但是它从结果中减去了 (dividend/2^31)。

实际上，当右移负整数时是算术右移（而且int类型是32位宽度），因此它会减去dividend >> 31，对于负的dividend来说，这个值是-1，而对于非负的dividend来说，这个值是0。

0x6666667 = (2^34 + 6)/10

对于 x < 0，我们有：x = 10*k + r，其中 -10 < r <= 0。

0x66666667 * (10*k+r) = (2^34+6)*k + (2^34 + 6)*r/10 = 2^34*k + 6*k + (2^34+6)*r/10

现在，对于负整数的算术右移将产生v / 2^n的下整数，因此

(0x66666667 * x) >> 34

导致

k + floor((6*k + (2^34+6)*r/10) / 2^34)

所以我们需要看到

-2^34 < 6*k + (2^34+6)*r/10 < 0

右边的不等式很容易，因为k和r都是非正数，且不同时为0。

对于左边的不等式，需要进行更多的分析。

r >= -9

因此，(2^34+6)*r/10的绝对值最多为2^34+6 - (2^34+6)/10。

|k| <= 2^31/10,

所以|6*k| <= 3*2^31/5。

现在需要验证

6 + 3*2^31/5 < (2^34+6)/10
1288490194   < 1717986919

没错，是真的。

- Daniel Fischer

---

感谢您的详细说明。 - Daniel Scocco

Answer 2

x SAR 31对于x的负值等于0xffffffff (-1)，对于正值等于0x00000000。

因此，如果被除数为负数，rsb会从结果中减去-1（相当于加1）。

假设你的被除数是-60。仅使用乘法和移位，你将得到结果-7，所以它会减去-1以获得预期的结果-6。

- Michael