关于 C 溢出,如何在 Python 中使用 64 位无符号整数数学?
How to use 64-bit unsigned integer math in Python, respecting C overflow?
我正在尝试在 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
正如我在代码中评论的那样,由于这是在字节串上定义的操作,因此您应该使用 bytes
实例作为参数。请注意,此算法有许多不同的实现。有些人在更新哈希值的步骤中使用 ^
(按位异或)而不是 +
,并且通常定义为使用通常为 32 位的 unsigned long
而不是您问题中的 C 版本使用明确的 64 位整数。
在Python中计算DJB2 hash时,要避免使用long算法。为此,您必须在每次迭代后执行 hash &= 0xFFFFFFFFFFFFFFFF
。
这是 Python 中 DJB2 的正确单行实现:
import functools, itertools
djb2 = lambda x: functools.reduce(lambda x,c: (x*33 + c) & ((1<<64)-1), itertools.chain([5381], x))
备注:
- 因为 Python 是一种脚本语言,执行
(x << 5) + x
而不是 x*33
效率并不高
((1<<64)-1)
只是 0xFFFFFFFFFFFFFFFF
的缩写
我正在尝试在 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
正如我在代码中评论的那样,由于这是在字节串上定义的操作,因此您应该使用 bytes
实例作为参数。请注意,此算法有许多不同的实现。有些人在更新哈希值的步骤中使用 ^
(按位异或)而不是 +
,并且通常定义为使用通常为 32 位的 unsigned long
而不是您问题中的 C 版本使用明确的 64 位整数。
在Python中计算DJB2 hash时,要避免使用long算法。为此,您必须在每次迭代后执行 hash &= 0xFFFFFFFFFFFFFFFF
。
这是 Python 中 DJB2 的正确单行实现:
import functools, itertools
djb2 = lambda x: functools.reduce(lambda x,c: (x*33 + c) & ((1<<64)-1), itertools.chain([5381], x))
备注:
- 因为 Python 是一种脚本语言,执行
(x << 5) + x
而不是x*33
效率并不高 ((1<<64)-1)
只是0xFFFFFFFFFFFFFFFF
的缩写