1

我的客户是一名 Python 程序员，我为他创建了一个 C++ 后端，其中包括许可证生成和检查。为了提高安全性，Python 前端还将执行许可证的有效性检查。

然而，许可证生成和检查算法基于散列方法，该方法依赖于整数具有固定字节大小的事实，并且对值进行位移不会扩展整数字节数。

这是一个简化的示例代码：

unsigned int HashString(const char* str) {
    unsigned int hash = 3151;
    while (*str != 0) {
        hash = (hash << 3) + (*str << 2) * 3;
        str++;
    }
    return hash;
}

如何将其翻译成 Python？直接翻译显然会产生不同的结果：

def hash_string(str):
    hash = 3151
    for c in str:
        hash = (hash << 3) + (ord(c) << 2) * 3
    return hash

例如：

hash_string("foo bar spam")  #  228667414299004
HashString("foo bar spam")   // 3355459964

编辑：PHP 也需要这样做，因为在线商店也应该能够生成有效的许可证。

4

2 回答 2

4

用 屏蔽散列值&：

def hash_string(str, _width=2**32-1):
    hash = 3151
    for c in str:
        hash = ((hash << 3) + (ord(c) << 2) * 3)
    return hash & _width

这会手动将散列缩减为大小。您只需要限制一次结果；并不是说那些更高的位对最终结果有影响。

演示：

>>> hash_string("foo bar spam")
3355459964
于 2013-09-18T21:15:14.143 回答
3

unsigned int这里的问题是当它过去时C 会自动翻转UINT_MAX，而 Pythonint只是不断变大。

最简单的解决方法是在最后纠正：

return hash % (1 << 32)

对于非常大的字符串，在每次操作后屏蔽可能会快一点，以避免最终int得到处理缓慢的巨大值。但是对于较小的字符串，这可能会更慢，因为调用%12 次而不是 1 次的成本很容易超过处理 48 位 int 的成本。

PHP 可能有同样的问题，也可能有不同的问题。

PHP 的默认整数类型是 C long。在 64 位 Unix 平台上，这比 大unsigned int，所以你必须使用与 Python 相同的技巧（或者，%或者&，以你更有意义的方式。）

但在 32 位 Unix 平台或 Windows 上，它的大小与unsigned int签名相同，这意味着您需要不同的技巧。你实际上不能4294967293直接表示，比如说（试试吧，你会得到-3的）。您可以使用 aGMP或BCMathinteger 代替默认类型（在这种情况下，它与 Python 中的基本相同），或者您可以编写自定义代码用于打印、比较等，将其-3视为4294967293.

请注意，我只是假设它int是 32 位，并且long是 32 位或 64 位，因为这在当今每个流行的平台上都是正确的。但 C 标准只要求int至少 16 位长，long至少 32 位且不短于int. 如果您需要处理int可能是 16 位（或 18 位！）的非常旧的平台，或者可能是 64 位或更多位的未来平台，您必须适当地调整您的代码。

于 2013-09-18T21:15:21.610 回答