javascript - 模拟整数溢出的最佳执行方式？

Question

我正在玩弄散列函数，移植一些经典，如 murmur 或 fnv 系列，并创建我自己的，真的很有趣。我知道 js 并不是一个理想的环境，但无论如何。

我遇到的最大障碍是 js 对大多数算术使用双精度数。我见过的几乎每一个散列函数都通过乘法来利用整数溢出。例如，我将输入 7 乘以一些大素数，如 0x5bd1e995，这种乘法将这个小输入的重要性放大到结果的每一位，这对于散列函数来说非常简洁。

不幸的是，当使用双精度进行数学运算时，这完全是平的，因为双精度不会像整数一样溢出（保留最低有效位），而是试图保留结果的大小（保留最高有效位），并且几乎与设计有关任何哈希函数。

我发现解决这个问题的几种方法是

1. 在乘法之前对输入取模以确保结果不超过 Number.MAX_SAFE_INTEGER
2. 将输入拆分为两个 16 位值并重新组合后进行乘法运算
3. 根据输入使用各种幻数，以确保我保持在整数的双倍范围内

问题是，这些都不是快速的并且将性能切成碎片。所以，提问时间：如果乘法几乎肯定会超过 Number.MAX_SAFE_INTEGER，是否有一种性能良好的方法来模拟 js 中的整数溢出行为？

标签： javascriptalgorithminteger-overflow

Answer 1

请查看Math.imul。

这会将数字乘以 32 位整数并简单地截断溢出位。