如何在Python中使用64位无符号整数数学,尊重C溢出?

问题描述 投票:3回答:1

我正在尝试在Python中实现djb2哈希。

这是在C:

/* djb2 hash http://www.cse.yorku.ca/~oz/hash.html */

uint64_t djb2(size_t len, char const str[len]) {
    uint64_t hash = 5381;
    uint8_t c;
    for(size_t i = 0; i < len; i++) {
        c = str[i];
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }
    return hash;
}

这是我在Python中的尝试:

from ctypes import c_uint64, c_byte, cast, POINTER

def djb2(string: str) -> c_uint64:
    hash = c_uint64(5381)
    raw_bytes = cast(string, POINTER(c_byte * len(string)))[0]
    for i in range(0, len(raw_bytes)):
        hash = c_uint64((((((hash.value << 5) & 0xffffffffffffffff) + hash.value) & 0xffffffffffffffff) + raw_bytes[i]) & 0xffffffffffffffff) # hash * 33 + c
    return hash

但是,我在两者之间得到了不同的结果,我怀疑是因为不同的溢出行为,或者其他数学差异。

在python版本中屏蔽的原因是试图强制溢出(基于this answer)。

python hash integer unsigned
1个回答
2
投票

您可以在纯Python中轻松实现由C代码运行的算法,而无需任何ctypes内容。只需使用常规的Python整数来完成所有操作,并在最后获取模数(高位不会影响您正在执行的操作的较低位):

def djb2(string: bytes) -> int:  # note, use a bytestring for this, not a Unicode string!
    h = 5381
    for c in string:    # iterating over the bytestring directly gives integer values
        h = h * 33 + c  # use the computation from the C comments, but consider ^ instead of +
    return h % 2**64    # note you may actually want % 2**32, as this hash is often 32-bit

正如我在代码中注释的那样,因为这是在字节串上定义的操作,所以应该使用bytes实例作为参数。请注意,此算法有许多不同的实现。有些人在更新哈希值的步骤中使用^(按位xor)而不是+,并且它通常被定义为使用unsigned long,它通常是32位而不是显式的64位整数,问题中的C版本使用。

© www.soinside.com 2019 - 2024. All rights reserved.