integer - 有符号 64 乘以 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

但是签名的案例给我带来了问题。假设执行签名版本的 udive 的等效 sdive 指令，我不太清楚如何处理余数和诸如此类的东西。

Answer 1

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

Hacker's Delight 这本书通常适合这类低级算术知识。我现在手头没有副本，但它的代码执行 64/64->64 给定 64/32->32 在线:http://www.hackersdelight.org/HDcode/newCode/divDouble.c

通过简单地获取输入的绝对值，进行无符号除法，然后如果输入具有不同的符号，则翻转结果位的符号来完成带符号的情况。这向我表明，这可能是最好的方法(证明正确性肯定比替代方法更容易)。您可能需要将股息作为可能的最小整数作为特殊情况，如果它不只是落空的话。