带符号的64位整数除以32位整数

Question

假设您有一个机器指令udive，它通过取（32位被除数 << 32）/ 32位除数来执行特殊情况下的64乘以32无符号除法，我们可以使用以下方法进行完整的64乘以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的有符号版本，我无法确定如何处理余数等内容。

- Joon

---

本能地感觉这是一个二进制补码问题。由于我不是专家，无法为您提供更多建议，但也许这是一个线索。 - Robert Harvey

Answer 1

感谢您的回答。我已经查看了《黑客的乐趣》。如果您查看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
}

- Joon

Answer 2

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

书籍《黑客的乐趣》通常对这种低级算术问题很有帮助。我目前手头没有一本副本，但它用于执行64/64->64和64/32->32的代码在线上可以找到：http://www.hackersdelight.org/HDcode/newCode/divDouble.c

这个代码通过简单地取输入的绝对值，进行无符号除法，然后翻转结果位的符号来处理有符号情况。这使我想到这可能是最好的方法（它肯定比另一种方法更容易证明正确）。如果不是刚好符合条件，您可能需要特殊处理被除数是最小可能整数的情况。

- pm215

Answer 3

你可以忽略divdi3调用divs的特殊优化情况；我想要引起注意的是，当divdi3需要进行全强度除法时，它会通过调用udivdi3来执行，而不是通过具有与udivdi3算法等效的带符号除法。

在Knuth vol 2中搜索，我发现他也基本上说，您可以通过取绝对值、进行无符号除法，然后修复符号位来进行带符号除法。这对我来说很直观，因为带符号的二进制补码数字没有无符号数字那样方便，即a == (a.h * 2^32) + a.l，所以不像通过分别操作两个半部分来组装64位操作那么容易。

前后调整不应该比无符号除法多很多额外的周期...

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

- pm215