散列溢和下溢在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位的位被丟失。