12

据我所知，大多数编译器会通过乘法然后向右移位来进行快速除法。例如，如果您检查这个 SO 线程，它会说当您要求 Microsoft 编译器除以 10 时，它会将除数乘以 0x1999999A（即 2^32/10），然后将结果除以 2^32（使用向右移动 32 次）。

（编者注：链接的答案是错误的，直到。编译器不会这样做，因为它并不适用于所有输入。编译器会进行乘法和移位，但使用更复杂的方式来确定魔法常数和移位计数： 为什么 GCC 使用在实现整数除法时乘以一个奇怪的数字？）

到现在为止还挺好。

但是，一旦我在 ARM 上使用 GCC 测试了相同的除以 10，编译器做了一些稍微不同的事情。首先它将被除数乘以 0x66666667 (2^34/10)，然后将结果除以 2^34。到目前为止，它与 Microsoft 相同，只是使用了更高的乘数。然而，在那之后，它从结果中减去 (dividend/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)
4

2 回答 2

12

然而，在那之后，它从结果中减去 (dividend/2^31)。

实际上，当右移负整数是算术右移（并且是 32 位宽）时，它减去dividend >> 31（-1对于负数）和 0 （对于非负被除数）。dividendint

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

是的，没错。

于 2013-04-25T15:27:36.957 回答
5

x SAR 310xffffffff对于 的负值x和0x00000000正值是(-1)。

因此，rsb如果股息为负，则从结果中减去 -1（与加 1 相同）。

假设您的股息是-60。只需乘法和移位，您就可以得到结果-7，因此它减去 -1 即可得到 的预期结果-6。

于 2013-04-25T15:21:59.230 回答