考虑到C溢出,如何在Python中使用64位无符号整数数学？

发布时间：2020-12-17 17:39:07 所属栏目：Python 来源：网络整理

导读：我正在尝试在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)

我正在尝试在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中轻松实现由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

正如我在代码中评论的那样,由于这是对字节串定义的操作,因此应使用字节实例作为参数.请注意,此算法有很多不同的实现.有些人使用^(按位异或)而不是在更新哈希值的步骤中使用,并且通常将其定义为使用无符号长型,通常为32位,而不是问题中C版本使用的显式64位整数.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!