32位有符号乘法，JavaScript中有64位结果

Question

我正在JavaScript中开发一个虚拟机，需要将两个有符号32位数与64位有符号结果相乘，作为两个32位有符号数（高32位和低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以使两者都为正数，执行无符号乘法，然后根据需要否定结果，但这种感觉像是一种无法理解的次优解。任何想法如何做得更好？将a和b分成两个有符号的16位数字，每个数字看起来都是合乎逻辑的，但随后我对如何执行其他操作没有任何错误感到遗憾。

p.s.如果您认为我的未签名实施也不理想，请随时指出。

Answer 1

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

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

之后，你可以做你的交叉乘法算法正常;结果的上半部分将是一个带符号的32位整数（因为它是其中一些已签名的产品的总和），而下半部分将是一个无符号的32位整数。解释它涉及到做相同的“诡计”。

顺便说一下，如果您在本机进行乘法运算的机器上查看本机整数的单个单词，您会看到什么，这相当自然。

Answer 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; 
    }; 
}