主要观点：在给定集合的 N 个元素中随机选整数，计算机用 32 位整数生成函数，需将其转为不大于 N 的索引，常见方法是取模运算（x % N），但除法较昂贵，还有一种将 32 位整数 x 与 N 相乘后右移 32 位（((uint64_t) x (uint64_t) N) >> 32）的方法更快，此方法通过将[0, 2^32)的整数映射到[0, N 2^32)的 N 的倍数来实现公平映射，且能证明其公平性，可纠正偏差，还提供了相关 C/C++代码及进一步阅读资料。

关键信息：

• 用取模运算实现将 32 位整数转为不大于 N 的索引，如uint32_t reduce(uint32_t x, uint32_t N) { return x % N; }。
• 更快的方法是将 32 位整数 x 与 N 相乘后右移 32 位，如uint32_t reduce(uint32_t x, uint32_t N) { return ((uint64_t) x * (uint64_t) N) >> 32; }。
• 证明公平性的方法：通过将[0, 2^32)的整数映射到[0, N * 2^32)的 N 的倍数，计算各区间内 N 的倍数个数，其个数为 ceil(2^32 / N)或 floor(2^32 / N)。
• 可纠正偏差的方法：用拒绝法，可参考相关快速洗牌函数的帖子。
• 提供了相关 C/C++代码的 GitHub 链接[https://github.com/lemire/fas...]及进一步阅读资料，如相关学术论文等。

重要细节：

• 在最近的 x64 处理器上，32 位除法吞吐量为每 6 个周期 1 条指令，延迟为 26 个周期；乘法吞吐量为每周期 1 条指令，延迟为 3 个周期。
• 在最近的 Intel 处理器（Skylake）上，乘法后移位的方法（即更快的映射方法）延迟约 4 个周期，吞吐量至少每 2 个周期 1 次调用。
• 多个项目如 Google Tensorflow、Stockfish、Microsoft Arriba 等采用了此方法，如 Google Tensorflow 的相关提交Switching the presized cuckoo map from using strict mod等。