有没有办法将整数值包装成整数范围 [min，max] 而不除法或取模?

Question

我的情况和这个问题一样，但我没有使用浮点数，而是使用整数。我觉得这种差异可能很重要，因为可能有一些小技巧可以用来将值包装到范围内。

将值包装到范围中的一个用例是为哈希表中的存储桶分配值，如下所示(范围[0,len(buckets)])：

bucket = buckets[hash(key) % len(buckets)]

如果我们不断向哈希表添加值，则优化此操作可能是值得的。

Answer 1

由于实际上不需要模数，因此有一个快捷方式可以将哈希映射到新范围。参见Lemire的FastRange。

// map a **full-width 32-bit** hash to [0,p) without division.
uint32_t fastrange32(uint32_t word, uint32_t p) {
return (uint32_t)(((uint64_t)word * (uint64_t)p) >> 32);
}

只需取 32x32 -> 64 位乘法的高半部分word * p. 如果所有word值都很小，则所有结果都将0，因此这仅适用于在整个 32 位范围内相当均匀分布word值。 哈希函数通常没问题。

我想这有点偏颇，但可以解决，请参阅 https://github.com/apple/swift/pull/39143

---

通常，桶的数量保持为 2 的幂。 这允许不需要的位被屏蔽掉。 (例如，如果有 16 个存储桶，则bucket_id = hash & 0xF。 缺点是每次调整表大小时，它要求存储桶数量增加一倍。