1

私は JavaScript で VM を開発しており、2 つの符号付き 32 ビット数値 (上位 32 ビットと下位 32 ビット) として格納された 64 ビット符号付きの結果で 2 つの符号付き 32 ビット数値を乗算する必要があります。

両方の数値を 16 ビットのペアに分割し、それらを乗算することで、符号なし数値に対しても同じことを行うことができました: a*b = (ah * 2^16 + al) * (bh * 2^16 + bl):

function mul_32_unsigned( a, b )
{
  var ah = a >>> 16;
  var bh = b >>> 16;
  var al = a & 0xFFFF;
  var bl = b & 0xFFFF;

  var mid = ah * bl + al * bh;
  var albl = al * bl;

  var imm = mid + ( albl >>> 16 );

  var carry = ( imm > 0xffffffff ) ? 0x10000 : 0;

  var lo = ( ( mid << 16 ) + albl ) >>> 0;
  var hi = ( ah * bh + ( imm >>> 16 ) + carry ) >>> 0;

  return [ lo, hi ];
}

ただし、符号付きの数値に対して同じことを行う方法がよくわかりません。私が考えることができる唯一のことは、負を否定するかa、b両方を正にし、符号なし乗算を実行し、必要に応じて結果を否定することですが、これは無知な次善の解決策のように感じます。それをより良くする方法についてのアイデアはありますか？aandをそれぞれ 2 つの符号付き 16 ビット数値に分割bすることは論理的に思えますが、残りを間違いなく実行する方法に途方に暮れています。

ps 私の署名なしの実装も最適ではないと思われる場合は、遠慮なく指摘してください。

4

2 に答える 2

5

符号付き 32 ビット整数を 2 つの 16 ビット整数に分割する正しい方法は、符号付き 16 ビットの上半分と符号なし 16 ビットの下半分を分割することです。上半分から、下半分に 2^16 を追加します (正になるように)。

たとえば、数値 -100000 は、上半分が -2 で下半分が 31072 になるはずです。再構築すると、-2 * 2^16 + 31072 == -131072 + 31072 == -100000 となります。

この後、交差乗算アルゴリズムを通常どおり実行できます。結果の上半分は符号付き 32 ビット整数 (一部は符号付きの積の合計であるため) になり、下半分は符号なし 32 ビット整数になります。それを解釈するには、同じ「トリック」を逆に行う必要があります。

ちなみに、これは、乗算をネイティブに実行するマシンでネイティブ整数の個々の単語を調べた場合に見られるもののかなり自然な解釈に対応しています。

于 2012-11-28T03:50:36.323 に答える