64位有符号乘法
我正在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位数字看起来都是合乎逻辑的，但是我对如何在没有任何错误的情况下执行其余部分感到失落。
ps如果您认为我的未签名实施也不理想，请随时指出。
将带符号的32位整数分成两个16位整数的正确方法是将有符号的16位上半部分和无符号的16位下半部分分开 - 并且需要对负数进行调整，方法是将负数减1从上半部分开始，并在下半部分加2 ^ 16（以使其为正）。
例如，数字-100000应该变为-2的上半部分和31072的下半部分。通过重构-2 * 2 ^ 16 + 31072 == -131072 + 31072 == -100000可以看到。
在此之后，您可以像往常一样进行交叉乘法运算; 结果的上半部分将是一个带符号的32位整数（因为它是其中一些已签名的产品的总和），而下半部分将是一个无符号的32位整数。 解释它涉及到做相同的“诡计”。
顺便说一下，这对应于一种相当自然的解释，即如果您在本机执行乘法的计算机上查看本机整数的单个单词，您会看到什么。
我发现自己也遇到了同样的问题，并没有找到完整的答案。 这不是微不足道的。 所以我提出了一个解决方案：
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;
};
}