高效的整数运算



我目前正在为一种可以编译成JavaScript的小语言编写编译器。在这种语言中,我非常希望使用整数,但是JavaScript只支持Number,它是一个双精度浮点值。那么,在JavaScript中实现整数的最有效方法是什么呢?与仅仅使用Number相比,这样做的效率如何?

特别是,溢出行为应该与其他语言一致:例如,向INT_MAX添加1应该得到INT_MIN。整数必须为32位或64位。
那么,在JavaScript中实现整数的最有效方法是什么?

原始数字类型是最有效的。许多现代JS引擎都支持JIT编译,所以它应该几乎和原生浮点运算一样高效。

特别是,溢出行为应该与其他语言一致:例如,向INT_MAX添加1应该得到INT_MIN。整数必须是32位或64位。

您可以通过注意JavaScript将"数字"转换为32位整数进行位操作来实现标准32位整数算术的语义。>>>(无符号右移)将其操作数转换为无符号32位整数,而其余(所有其他移位和位与/或)将其操作数转换为有符号32位整数。例如:

  • 0xFFFFFFFF | 0生成-1(有符号铸型)
  • (0xFFFFFFFF + 1) | 0产生0(溢出)
  • -1 >>> 0生成0xFFFFFFFF(无符号转换)

我在Javascript中找到了这个BigIntegers的实现:http://www-cs-students.stanford.edu/~tjw/jsbn/

也许这会有帮助?

编辑:另外,Google Closure库实现了64位整数:http://code.google.com/p/closure-library/source/browse/trunk/closure/goog/math/long.js

这些本质上只是生成方便的对象,而不会做任何事情来提高基本数据类型的效率。

在现代CPU上,如果你将整数值限制在+- 2^52的范围内,那么使用double将不会比使用long效率低。

double IEE754类型有53位尾数,所以你可以很容易地表示32位整数范围。

在任何情况下,Javascript的其余部分将比用于处理算术的单个CPU指令更成为瓶颈。

所有的数字都是数字。这是没有办法的。JavaScript没有字节或int类型。要么处理这些限制,要么使用更低级的语言来编写编译器。

如果你想实现这一点,唯一明智的选择是编辑一个JavaScript解释器(比如V8)并扩展JS以允许访问本机C字节。

你可以选择JavaScript的数字类型,这可能是使用你的CPU的原语计算的,或者你可以选择分层一个完整的操作符和函数包,什么不是在模拟的一系列位…?

…如果你关心的是性能和效率,那就坚持使用双打。

最有效的方法是使用数字,并添加操作,以确保对模拟整数的操作将得到整数结果。例如,除法必须向下舍入,乘法必须检查溢出或掩码以适应整数范围。

这当然意味着你的语言中的浮点运算要比整数运算快得多,这就违背了使用整数类型的大部分目的。

注意ECMA-262 Edition 3添加了Number.prototype。toFixed,这需要一个精确的参数,告诉我们有多少小数点后的数字为秀。用好这个方法,你就能不会介意之间的差距有限精度以2为底"任意"或"适当"的精度我们每天都用的以10为底。- Brendan Eich

相关内容

  • 没有找到相关文章

最新更新