1

我正在用 JavaScript 开发一个 VM，需要将两个带符号的 32 位数字与存储为两个 32 位带符号数字（高 32 位和低 32 位）的 64 位带符号结果相乘。

我设法通过将两个数字拆分为 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使两者都为正数，执行无符号乘法，然后在需要时否定结果，但这感觉像是一个毫无头绪的次优解决方案。关于如何做得更好的任何想法？将a和b分成两个有符号的 16 位数字似乎是合乎逻辑的，但是我对如何在没有任何错误的情况下执行其余部分感到迷茫。

ps 如果您认为我的未签名实现也不是最理想的，也请随时指出这一点。

4

2 回答 2

5

将带符号的 32 位整数拆分为两个 16 位整数的正确方法是作为带符号的 16 位上半部分和无符号的 16 位下半部分 - 您需要通过减去一个来对负数进行调整从上半部分开始，并在下半部分加上 2^16（以使其为正）。

例如，数字 -100000 应该成为 -2 的上半部分和 31072 的下半部分。通过重构 -2 * 2^16 + 31072 == -131072 + 31072 == -100000 可以看到。

在此之后，您可以正常执行交叉乘法算法；结果的上半部分将是一个有符号的 32 位整数（因为它是其中一些有符号的乘积之和），而下半部分将是一个无符号的 32 位整数。解释它涉及反向执行相同的“技巧”。

顺便说一句，这对应于一个相当自然的解释，如果你在一台机器上进行本机乘法运算时查看本机整数的各个单词，你会看到什么。

于 2012-11-28T03:50:36.323 回答
2

我发现自己遇到了同样的问题，但没有找到完整的回复。这不是微不足道的。所以我在这里提出了一个解决方案：

if (!Math.umul32_64) {
    Math.umul32_64 = function (a, b, result) {
        if (result === undefined) result = [0, 0];

        a >>>= 0;
        b >>>= 0;

        if (a < 32767 && b < 65536) {
            result[0] = a * b;
            result[1] = (result[0] < 0) ? -1 : 0;
            return result;
        }

        var a00 = a & 0xFFFF, a16 = a >>> 16;
        var b00 = b & 0xFFFF, b16 = b >>> 16;

        var c00 = a00 * b00;
        var c16 = (c00 >>> 16) + (a16 * b00);
        var c32 = c16 >>> 16;
        c16 = (c16 & 0xFFFF) + (a00 * b16);
        c32 += c16 >>> 16;
        var c48 = c32 >>> 16;
        c32 = (c32 & 0xFFFF) + (a16 * b16);
        c48 += c32 >>> 16;

        result[0] = ((c16 & 0xFFFF) << 16) | (c00 & 0xFFFF);
        result[1] = ((c48 & 0xFFFF) << 16) | (c32 & 0xFFFF);
        return result;
    };
}

if (!Math.imul32_64) {
    Math.imul32_64 = function (a, b, result) {
        if (result === undefined) result = [0, 0];

        if (a == 0) return result[0] = result[1] = 0, result;
        if (b == 0) return result[0] = result[1] = 0, result;

        a |= 0, b |= 0;

        if ((a >= -32768 && a <= 32767) && (b >= -32768 && b <= 32767)) {
            result[0] = a * b;
            result[1] = (result[0] < 0) ? -1 : 0;
            return result;
        }

        var doNegate = (a < 0) ^ (b < 0);

        Math.umul32_64(Math.abs(a), Math.abs(b), result);

        if (doNegate) {
            result[0] = ~result[0];
            result[1] = ~result[1];
            result[0] = (result[0] + 1) | 0;
            if (result[0] == 0) result[1] = (result[1] + 1) | 0;
        }

        return result;
    };
}
于 2014-05-04T16:59:16.900 回答