bit signed multiplication with a 64
I'm developing a VM in JavaScript and need to multiply two signed 32-bit numbers with a 64-bit signed result stored as two 32-bit signed numbers (upper 32-bit and lower 32-bit).
I managed to do the same for unsigned numbers by splitting both numbers to 16-bit pairs and multiplying those: 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 ];
}
However, I don't really understand how to do the same thing for signed numbers. The only thing I can think of is negating any negative a or b to make both positive, perform the unsigned multiplication, then negate the result if needed, but this feels like a clueless suboptimal solution. Any ideas on how to do it better? Splitting a and b into two signed 16-bit numbers each would seem logical, but then I feel lost on how to perform the rest without any mistakes.
ps If you think my unsigned implementation is suboptimal as well, please feel free to point that out, too.
The correct way to split a signed 32-bit integer into two 16-bit integers is as a signed 16-bit upper half, and an unsigned 16-bit lower half — and you need to make an adjustment for negative numbers, by subtracting one from the upper half, and adding 2^16 to the lower half (so as to make it positive).
For example, the number -100000 should become an upper half of -2 and a lower half of 31072. You can see by reconstructing that -2 * 2^16 + 31072 == -131072 + 31072 == -100000.
After this, you can do your cross-multiply algorithm as normal; the upper half of the result will be a signed 32-bit integer (because it's the sum of products some of which are signed), and the lower half will be an unsigned 32-bit integer. Interpreting it involves doing the same "trick" in reverse.
This corresponds, by the way, to a fairly natural interpretation of what you would see if you looked at the individual words of the native integers on a machine doing the multiplication natively.
I found myself with this same problem, and didn't found the complete response. It wasn't trivial. So I put here a solution:
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;
};
}
下一篇: 64位有符号乘法