由32整数除法签署64 [英] Signed 64 by 32 integer division

问题描述

假设你有一个机器指令udive通过采用（32位被除数< 32）/ 32位除数来进行64×32无符号除法的特殊情况，我们可以使用以下方法进行完整的64乘32除法： / p>

Assuming you have a machine instruction udive that does a special case 64 by 32 unsigned division by taking a (32bit dividend << 32) / 32bit divisor, we can do a full 64 by 32 division using the following:

// 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的签名版本，我无法弄清楚如何处理余数等等。

However the signed case is giving me problems. Assuming an equivalent sdive instruction that does the signed version of udive, I can't quite work out how to deal with the remainders and whatnot.

推荐答案

你可以忽略divdi3调用div的特殊优化情况;我想提请注意的事实是，当divdi3需要进行全强度除法时，它通过调用udivdi3而不是通过使用等效于udivdi3算法的signed-division来实现。

You can ignore divdi3's special optimisation case of calling divs; the thing I wanted to draw attention to was the fact that when divdi3 needs to do full-strength division it does it by calling udivdi3 rather than by having a signed-division equivalent to the udivdi3 algorithm.

看看Knuth vol 2我看到他也基本上说你通过取绝对值，做无符号除法然后修复符号位的过程来进行符号划分。这对我来说很直观，因为有符号的2s补码没有方便的属性，即无符号数的a ==（ah * 2 ^ 32）+ al，所以通过操作组装64位操作并不容易分别是两半。

Looking in Knuth vol 2 I see that he also basically says that you do signed division by the process of taking absolute values, doing an unsigned divide and then fixing up the sign bit afterwards. This makes intuitive sense to me, because signed 2s complement numbers don't have the convenient property that a == (a.h * 2^32) + a.l that unsigned numbers do, so it's not as easy to assemble 64 bit operations by operating on the two halves separately.

前后摆弄不应该超过无符号除数的额外周期......

The before-and-after fiddling shouldn't be that many extra cycles over the unsigned divide...

PS：无论如何，这是什么怪人CPU？ ： - ）

PS: what weirdo CPU is this, anyway? :-)

这篇关于由32整数除法签署64的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！