3

(32 ビット被除数 << 32) / 32 ビット除数を使用して 64 × 32 の符号なし除算を行う特別なケースのマシン命令 udiv があると仮定すると、以下を使用して完全な 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

しかし、署名されたケースは私に問題を与えています。udiv の署名付きバージョンを実行する同等の sdive 命令を想定すると、残りの部分などを処理する方法がわかりません。

4

3 に答える 3

0

回答ありがとうございます。Hacker's Delight を見てきました。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
}
于 2009-07-07T01:29:15.790 に答える
0

div を呼び出すという divdi3 の特別な最適化ケースは無視できます。私が注意を喚起したかったのは、divdi3 が完全な強度の除算を行う必要がある場合、udivdi3 アルゴリズムと同等の符号付き除算を使用するのではなく、udivdi3 を呼び出すことによってそれを行うという事実です。

Knuth vol 2 を見ると、彼は基本的に、絶対値を取得し、符号なし除算を行い、その後符号ビットを修正するプロセスによって符号付き除算を行うと言っていることがわかります。符号付きの 2 の補数には、符号なしの数値が持つ a == (ah * 2^32) + al という便利なプロパティがないため、これは直感的に理解できます。 2 つの半分を別々に。

前後のいじりは、符号なし除算でそれほど多くの余分なサイクルであってはなりません...

PS: とにかく、これは何の奇妙な CPU ですか? :-)

于 2009-07-07T18:47:49.433 に答える
0

どの変数が 32 ビットで、どれが 64 ビットで、比較が符号付きか符号なしかが明示されていれば、符号なしコードは読みやすくなると思います。

Hacker's Delightという本は、一般的に、この種の低レベルの算術演算に適しています。現時点では手元にコピーがありませんが、64/32->32 を指定して 64/64->64 を実行するためのコードはオンラインです: http://www.hackersdelight.org/HDcode/newCode/divDouble. c

これは、入力の絶対値を取得し、符号なし除算を行い、入力の符号が異なる場合は結果ビットの符号を反転するだけで、符号付きのケースを実行します。これは、これがおそらく最良のアプローチであることを示唆しています (別の方法よりも正しいことを証明する方が確かに簡単です)。ウォッシュで落ちない場合は、被除数が可能な限り最小の整数であるという特殊なケースが必要になる場合があります。

于 2009-07-06T22:26:34.390 に答える