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