algorithm - 从随机位序列生成随机整数

Question

非常基本的问题，但我似乎无法在 Google 上找到答案。标准 PRNG 将生成一系列随机位。我将如何使用它来生成一系列随机整数，这些随机整数在 [0, N) 范围内具有均匀的概率分布？此外，每个整数应使用(期望值)log_2(N) 位。

Answer 1

如果你想要一个介于 1 和 N 之间的随机数:

• 您计算将 N 转换为二进制数需要多少位。那是:

  n_bits = ceiling(log_2(N))
  

  其中 ceiling 是“向上舍入”操作。 (例如:天花板(3)= 3，天花板(3.7)= 4)

• 您选择随机二进制列表的前 n_bit 并将它们更改为十进制数。

• 如果您的十进制数大于 N，那么...您可以丢弃它并使用 n_bits 下一位再次尝试，直到它起作用为止。

N = 12 的例子:

• n_bits = ceiling(log_2(12)) = 4

• 您取随机位序列的前 4 位，可能是“1011”

• 您将“1011”转换为十进制数，得到 13。高于 12，不好。所以:

• 取随机序列中接下来的 4 位，可能是“1110”。

• 将“1110”转换为小数，得到 7。行得通!

希望对您有所帮助。