乘法时避免整数溢出的有效方法？
乘法时避免整数溢出的有效方法？
提问于 2010-05-05 03:02:26
我正在研究一个哈希函数，它将一个字符串作为输入。
现在，我正在做一个循环，在hash (一个int变量)中乘以一个值，然后将当前字符的ASCII代码添加到混合中。
hash = hash * seed + string[i]但有时，如果字符串足够大，有一个整数溢出，我可以做什么来避免它，同时保持相同的哈希结构？也许在循环中包含一点操作？
回答 4
Stack Overflow用户
发布于 2010-05-05 03:28:32
像这样的散列函数应该会溢出。你必须声明"hash“没有签名。如果你真的需要一个int而不是简单的使用hash & 0x7fffffff。查看Fowler-Noll-Vo algorithm，你会在那里找到源代码的链接。
Stack Overflow用户
发布于 2010-05-05 03:28:47
您的问题有许多可能的解释，正如评论所指出的，您可能需要澄清。
然而，唯一合理的解释是，您希望将散列值限制在指定的范围内。假设如此，那么如果范围是0到HASH_TABLE_SIZE - 1，那么：
hash = (hash * seed + string[i]) % HASH_TABLE_SIZE ;或者，如果表大小是2的幂，则使用掩码：
#define HASH_TABLE_SIZE (0x01<<8) // 2^8 (256) table
#define HASH_MODULO_MASK (HASH_TABLE_SIZE - 1)
...
hash = (hash * seed + string[i]) & HASH_MODULO_MASK ;Stack Overflow用户
发布于 2010-05-05 03:06:43
为什么不使用long来存储结果呢？然后，您可以应用such as this one技术来检测溢出
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2768183
复制相关文章
相似问题
腾讯云开发者
