javascript 32位整数乘法模拟
我只想要像32位整数那样的整数乘以溢出。
一些文章很容易喜欢使用按位操作
function add32bit( a, b )
{
return (a+b)|0;
}就像这样。
function mul32bit( a, b )
{
return (a*b)|0;
}但这不是工作。
在允许整数溢出32位整数系统中。
计算
12312311 * 1231231211 = -236858179但是使用javascript
(12312311 * 1231231211)|0 = -236858180有一种方法可以精确地计算。
回答 1
Stack Overflow用户
发布于 2015-06-27 09:41:27
解决方案(?)
按照Richie Frame的提示，我尝试使用Karatsuba algorithm来编写一个函数，该函数将两个整数相乘，并将结果作为带符号的32位整数返回。
// base algorithm from: https://en.wikipedia.org/wiki/Karatsuba_algorithm
// modified to discard values unneccessary for 32-Bit-operations
function int32_mul(x, y)
{
// We use B = 2 and m = 16, because it will make sure that we only do multiplications with
// 16 Bit per factor so that the result must have less than 32 Bit in total (which fits well
// into a double).
var bm = 1 << 16;
x0 = x % bm;
x1 = (x - x0) / bm;
y0 = y % bm;
y1 = (y - y0) / bm;
// z1 + z0. We can discard z2 completely as it only contains a value out of our relevant bounds.
// Both z1 and z0 are 32 Bit, but we shift out the top 16 Bit of z1.
return (((x1 * y0 + x0 * y1) << 16) + (x0 * y0)) | 0;
}我也运行了一些测试，以确保它的工作，但我不是该领域的专业人士，因此我不能保证它将工作在所有组合。我的大脑对这个问题有点糊涂了。
var tests = [
[ 0, 0, 0 ],
[ 0, 1, 0 ],
[ 1, 1 << 8, 256 ],
[ 1, 1 << 16, 65536 ],
[ 1, 1 << 24, 16777216 ],
[ 1, 0x7fffffff, 2147483647 ],
[ 1, 0x80000000, -2147483648 ],
[ 1, 0xffffffff, -1 ],
[ 2, 1 << 8, 512 ],
[ 2, 1 << 16, 131072 ],
[ 2, 1 << 24, 33554432 ],
[ 2, 0x80000000, 0 ],
[ 2, 0x7fffffff, -2 ],
[ 2, 0xffffffff, -2 ],
[ 256, 256, 65536 ],
[ 65536, 65536, 0 ],
[ -2, 2, -4 ],
[ -65536, 65536, 0 ],
[ -2, -2, 4 ],
[ -2147483648, 1, -2147483648 ],
[ -2147483649, 1, 2147483647 ],
[ 12312311, 1231231211, -236858179 ],
];
for (var i = 0; i < tests.length; ++i)
{
var test = tests[i];
if (int32_mul(test[0], test[1]) !== test[2])
{ console.log(test[0], '*', test[1], '!==', test[2]); }
}如果有更专业的人发现了这一点，请留下评论和/或给我们更多的测试用例。
另外，我也不能说这个函数接受什么样的值。我非常肯定它对所有有符号的32位整数都能很好地工作，但它也可以对无符号的32位整数工作，甚至可能是任何总共不超过68位(我们拆分出的16位+ 52 Bits)的整数组合(包括负数和正数，因为符号有自己的双精度位)。
问题说明
解释一下为什么JavaScript会给我们一个错误的结果。我用C语言运行了一些简单的测试(在http://ideone.com/ELSgD0上摆弄它)：
#include <stdio.h>
#include <stdint.h>
int main(void) {
printf("%d\n", (int32_t)(12312311L * 1231231211L));
printf("%llu\n", (uint64_t)12312311L * 1231231211L);
printf("%.32f\n", 12312311. * 1231231211.);
printf("%.8f\n", 15159301582738621.);
return 0;
}输出：
-236858179
15159301582738621
15159301582738620.00000000000000000000000000000000
15159301582738620.00000000Javascript对所有计算(即使是整数计算)都使用双精度。从上面的测试中，我得出结论，double不能具有值15159301582738621。
这是因为浮点数据类型如float (32位)、double (64位)和quad (128位)的工作方式。基本上，它们不存储精确值，而是以x * 2^y的形式存储值的x和y值，这使得它们既可以存储非常大的值，也可以存储非常小的值。我们(人类)过去对于非常大和非常小的数字都有类似的语法，例如1e9代表十亿，1e-5代表0.00001，而e是* 10^的快捷方式。
现在假设您计算10001 * 10001，它显然是100020001，但是假设您只能存储5位数和一个指数。要存储结果，您必须对其进行近似，并使用例如1.0002e8或10002e4。如你所见，你必须忘记结尾的1。实际上，你的例子中的双精度问题非常相似，只是规模更大，基数是2而不是10。
最后两个printf语句证明doubles不能保存值15159301582738621，这是您的示例计算的确切结果。如果你尝试使用12312311 * 1231231212 (第二个数字的末尾是2而不是1)，你会发现并不是这个范围内的所有数字都可以存储为双精度数，因为这个计算在你的函数中工作得很好。
https://stackoverflow.com/questions/31087787
复制相似问题
腾讯云开发者
