python-3.x - 在 Python3 中重新创建 JS 按位整数处理

Question

我需要将哈希函数从 JavaScript 转换为 Python。

函数如下:

function getIndex(string) {
        var length = 27;
        string = string.toLowerCase();
        var hash = 0;
        for (var i = 0; i < string.length; i++) {
                hash = string.charCodeAt(i) + (hash << 6) + (hash << 16) - hash;
        }
        var index = Math.abs(hash % length);
        return index;
}

console.log(getIndex(window.prompt("Enter a string to hash")));

此函数是 Objectively Correct™。它本身就是完美的。我无法改变它，我只能重新创建它。无论它输出什么，我的 Python 脚本也必须输出。

但是 - 我有几个问题，我认为这与这两种语言处理有符号整数的方式有关。

JS 按位运算符将其操作数视为 32 位序列。然而，Python 没有位限制的概念，并且像一个绝对的疯子一样继续运行。我认为这是两种语言之间的一个重要区别。

我可以通过使用 hash & 0xFFFFFFFF 将其屏蔽为 32 位来限制 Python 中 hash 的长度。

如果 hash 高于 0x7FFFFFFF，我也可以用 hash = hash ^ 0xFFFFFFFF (或 hash = ~hash - 他们似乎都做同样的事情)。我相信这会模拟负数。

我使用一个名为 t 的函数将这两个限制应用于哈希。

到目前为止，这是我的 Python 代码:

def nickColor(string):
    length = 27

    def t(x):
        x = x & 0xFFFFFFFF
        if x > 0x7FFFFFFF:
            x = x ^ 0xFFFFFFFF
        return x

    string = string.lower()
    hash = t(0)
    for letter in string:
        hash = t(hash)
        hash = t(t(ord(letter)) + t(hash << 6) + t(hash << 16) - t(hash))
    index = hash % length
    return index

它似乎一直工作到散列需要变为负值为止，此时两个脚本出现分歧。这通常发生在字符串中大约 4 个字母处。

我假设我的问题在于在 Python 中重新创建 JS 负数。我该如何告别这个问题？

Answer 1

这是一个有效的翻译:

def nickColor(string):
    length = 27

    def t(x):
        x &= 0xFFFF_FFFF
        if x > 0x7FFF_FFFF:
            x -= 0x1_0000_0000
        return float(x)

    bytes = string.lower().encode('utf-16-le')
    hash = 0.0
    for i in range(0, len(bytes), 2):
        char_code = bytes[i] + 256*bytes[i+1]
        hash = char_code + t(int(hash) << 6) + t(int(hash) << 16) - hash
    return int(hash % length if hash >= 0 else abs(hash % length - length))

重点是，只有移位 ( << ) 被计算为 32 位整数运算，它们的结果是 converted back to double在输入加法和减法之前。我不熟悉这两种语言的 double 浮点表示规则，但可以安全地假设在所有个人计算设备和 Web 服务器上，这两种语言都是相同的，即 double-precision IEEE 754 .对于非常长的字符串(数千个字符)，散​​列可能会丢失一些精度，这当然会影响最终结果，但在 JS 和 Python 中的方式相同(不是 Objectively Correct™ 函数的作者的意图，但是它就是这样儿的…)。最后一行更正了 % 的不同定义。 JavaScript 中负操作数的运算符和 Python .

此外(感谢 Mark Ransom 的提醒)，要完全模拟 JavaScript，还需要考虑其编码，即 UTF-16，但带有 surrogate pairs。处理为好像它们由 2 个字符组成。将字符串编码为 utf-16-le您确保每个 16 位“字”中的第一个字节是最低有效字节，另外，您不会得到 BOM如果你使用 utf-16 你会得到tout court(谢谢 Martijn Pieters)。