有符号 64 x 32 整数除法

Question

假设您有一个机器指令 udive，它通过采用 (32 位被除数 << 32) / 32 位除数来执行特殊情况 64 x 32 无符号除法，我们可以使用以下命令执行完整的 64 x 32 除法：

// assume: a / b guaranteed not to overflow
a = 64bit dividend, a.h & a.l are hi & lo 32bits respectively
b = 32bit divisor

q1 = udive(a.h, b)  // (a.h << 32) / b
r1 = -(q1 * b)      // remainder of the above, shortcut since a.h & 0xffffffff == 0
q2 = a.l / b        // a.l / b using regular unsigned division
r2 = a.l - (q2 * b) // remainder of the above
q = q1 + q2
r = r1 + r2

// r < r2, r overflowed and is >32bits, implies r > b since b is 32bits
// r >= b, quotient too small by 1, adjust
if (r < r2) or (r >= b)
    q = q + 1
return q

但是有符号情况给我带来了问题。 假设有一个等效的 sdive 指令执行 udive 的签名版本，我无法完全弄清楚如何处理余数等。

Answer 1

我认为，如果明确说明哪些变量是 32 位、哪些变量是 64 位以及比较是有符号的还是无符号的，那么你的无符号代码会更容易阅读。

黑客之乐这本书通常适合这类低级算术知识。 我目前手头没有副本，但它在给定 64/32->32 的情况下执行 64/64->64 的代码在线： http://www.hackersdelight.org/HDcode/newCode/divDouble.c

这通过简单地取绝对值来完成签名的情况输入，进行无符号除法，然后如果输入具有不同的符号则翻转结果位的符号。 这对我来说这可能是最好的方法（它肯定比其他方法更容易证明正确）。 您可能需要将股息作为特殊情况，使其成为可能的最小整数（如果它不会随波逐流）。

Answer 2

谢谢回答。 我看过《黑客之乐》。 如果您查看 HD 中的 divdi3 函数，就会发现当除数为 32 位并且已知结果不会溢出时，会调用 DIVS（64/32->32 指令）。 我所在的机器没有通用的 64/32->32 指令，它有上面提到的特殊情况。 上面的 64/32->32 函数是我在未签名情况下对 DIVU 的实现，所以我试图为 DIVS 找出类似的东西。

我可以忘记 DIVS 路径，但这是绝大多数常见的情况，我想尽可能多地使用它，这只是一个棘手的实现。

很抱歉伪代码不清楚，但所有内容都是无符号的，而且大部分都是 32 位的。

DIVU(uint64 a, uint32 b) {
// assume: a / b guaranteed not to overflow
// a = 64bit dividend, a.h & a.l are hi & lo 32bits respectively
// b = 32bit divisor

uint32 q1 = udive(a.h, b)      // (a.h << 32) / b
uint32 r1 = -(q1 * b)          // remainder of the above, shortcut for (a.h << 32) - (q1 * b) since (a.h << 32) & 0xffffffff == 0
uint32 q2 = a.l / b            // a.l / b using regular unsigned division
uint32 r2 = a.l - (q2 * b)     // remainder of the above
uint32 q = q1 + q2
uint32 r = r1 + r2

// r < r2, r overflowed and is >32bits, implies r > b since b is 32bits
// r >= b, quotient too small by 1, adjust
if (r < r2) or (r >= b)
        q = q + 1
return q
}

Answer 3

可以忽略divdi3调用div的特殊优化情况； 我想提请注意的是，当 divdi3 需要进行全强度除法时，它是通过调用 udivdi3 而不是通过与 udivdi3 算法等效的有符号除法来实现的。

看看 Knuth vol 2，我发现他基本上还说，你可以通过取绝对值的过程来进行有符号除法，进行无符号除法，然后修复符号位。 这对我来说很直观，因为有符号的 2s 补数不具有无符号数 a == (ah * 2^32) + al 所具有的便利属性，因此通过操作来组装 64 位操作并不容易两半分开。

前后摆弄不应该在无符号除法上有那么多额外的周期...

PS：这到底是什么奇怪的CPU？ :-)