c++ - 为什么 BKDFHash 不关心超出范围的问题？

Question

unsigned int BKDRHash(const std::string& str){
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;

for(std::size_t i = 0; i < str.length(); i++)
{
    hash = (hash * seed) + str[i];
}

return hash;}

为什么上面代码中hash是否超出了unsigned int的范围我们不需要关心呢？我已经看到几个示例代码对溢出问题没有任何作用。为什么它仍然有效？当值 hash 超出 unsigned int 的范围时会发生什么？

Answer 1

之所以有效，是因为根据标准，unsigned 整数类型实际上不会发生溢出:

3.9.1 Fundamental types [basic.fundamental]

Unsigned integers shall obey the laws of arithmetic modulo 2ⁿ where n is the number of bits in the value representation of that particular size of integer.⁴⁸

48. This implies that unsigned arithmetic does not overflow because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting unsigned integer type.

例如:如果 unsigned int 算术结果 x 会超过 UINT_MAX，则结果恰好是:

x % (UINT_MAX+1)

从而在 0...UINT_MAX 内为您留下结果