给定一个生成真正随机 32 位数字的函数 R，我想要一个函数返回 0 到 n 范围内的随机整数，其中 n 是任意的(小于 2^32)。
该函数必须以相等的概率生成 0 到 n 的所有值。
我想要一个在恒定时间内执行的函数，没有 if 语句或循环，所以像 Java Random.nextInt(n) 函数这样的东西已经过时了。
我怀疑简单的模数不能完成这项工作，除非 n 是 2 的幂——我说得对吗？
我接受了 Jason 的回答，尽管它需要一个不确定持续时间的循环，因为它似乎是实践中使用的最佳方法并且基本上回答了我的问题。但是，我仍然对本质上具有确定性并保证终止的任何算法(即使效率较低)感兴趣，例如 Mark Byers 所指出的。
最佳答案
如果不丢弃源中的某些值，则无法执行此操作。例如，一个大小为 2^32 的集合不能分成三个大小相等的集合。因此，如果不丢弃一些值并迭代直到产生一个未丢弃的值，就不可能做到这一点。
所以，只需使用这个(伪代码):
rng is random number generator produces uniform integers from [0, max)
compute m = max modulo (n + 1)
do {
draw a random number r from rng
} while(r >= max - m)
return r modulo (n + 1)
实际上我扔掉了导致问题的分布的顶部。如果 rng 在 [0, max) 上是统一的，那么这个算法在 [0, n]
关于algorithm - 0 到 n 范围内的随机数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1972252/