散列溢和下溢在RobertSedwick书

Question

< 1>如果密钥W-位整数，我们可以通过2至< 2>功率W的将其转换为 浮点数和除法得到 浮点0和1之间的点数，然后乘以M.

< 3>如果浮点运算是昂贵的并且该数字不是 如此大到引起< 4>溢出，就可以实现相同的结果用 整数算术运算：乘以密钥< 5> M，然后 右移w位除以2的w次方（或者，如果乘法运算将溢出，然后乘法运算）。除非密钥均匀分布在范围 中，否则这些函数对于散列无用 ，因为散列值仅由密钥的前导数字确定。

我念叨hasing罗伯特Sedwick书算法的C++

这里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位的位被丢失。