c - RobertSedwick 书中的哈希溢出和下溢

Question

<1>If the keys are w-bit integers, we can convert them to floating-point numbers and divide by 2 to <2>power of w to get floating-point numbers between 0 and 1, then multiply by M.

<3>If floating-point operations are expensive and the numbers are not so large as to cause <4>overflow, we can accomplish the same result with integer arithmetic operations: Multiply the key <5>by M, then shift right w bits to divide by 2 to power of w (or, if the multiply would overflow, <6>shift then multiply). Such functions are not useful for hashing unless the keys are evenly <7>distributed in the range, because the hash value is determined only by the leading digits of the <8>keys.

我正在阅读 Robert Sedwick 的《C++ 算法》一书中有关 hasing 的内容

这里 M 是哈希容器的大小，例如容器[M]

1. 我对上述文本的问题是，作者在这种情况下在第 4 行谈论溢出和下溢？这里作者说的是乘法是否会溢出，移位然后乘法？移动什么以及乘以什么

2. 要求通过简单的示例来理解第 3 行至第 8 行？

谢谢

Answer 1

整数乘法有可能溢出和丢失信息，例如执行 32 位无符号算术时溢出的示例:

2 ^ 31 = 0x80000000
(2 ^ 31 * 2 ^ 31) = 2 ^ 62 = 0x4000000000000000

由于 32 位可表示的最大数字为 0xFFFFFFFF = 2 ^ 32 - 1，因此上述计算的结果将为 0，因为 32 位以上的位会丢失。