编程珠玑P135页

Question

中间有段话是这样说的：直观的映射t*bins/maxval可能导致数值溢出，因此，我们采用下述代码所示的更安全的映射：

void insert(t)
    i = t / (1 + maxval/bins)
    bin[i] = rinsert(bin[i], t)

请问：为什么会溢出？（我觉得可能是先乘后除的原因），另外，为什么i = t / (1 + maxval/bins)要加上1呢？

Answer 1

溢出你的想法是对的 坐等加一的答案

Answer 2

加一是当maxval不是bins的倍数的情况下，仍然能将 0..maxval 分布到各个bins中去（虽然不严格均分），相当于每个bin（或bucket）都有了额外的空间。

举个例子： 假设maxval为50, bins为3。若无额外空间的话，只能分别映射 [0..15], [16..31], [32..47]，若t in [48..50]，就溢出了。

PS 我想书中所说的溢出也有这个意思。

Answer 3

没有看过书， 个人觉的原因如下： t*bins/maxval 会溢出 ， 是因为 t * bins ， 如果t 和 bins 都为 INT_MAX ， 直接乘就溢出了

加1的原因一般有二个吧：

1. 避免除0
2. 避免除数太小 ， 发生溢出 ， 比如 maxval/bins = 1e-10 , 那么 t / ( maxvla / bins) 就等于 t ^ 10 ， 然后就溢出了 ， 加上1之后 ， 结果就在 1 ~ t 之间了 。