问生成等概率数

EN

您需要的洞察力是，您的bin()函数返回一个二进制数字或“位”。调用它一次会给出0或1。如果你两次调用它，就会得到两位b0和b1，它们可以合并为b1 * 2 + b0，以相同的概率给出0、1、2或3中的一个。如果您三次调用它，您将得到三位b0、b1和b2。把它们放在一起，得到b2 * 2^2 + b1 * 2 + b0，给出一个{0，1，2，3，4，5，6，7}的成员，概率相等。依此类推，你想要多少就多少。

您的范围a，b有m = b-a+1值。您只需要足够的位来生成介于0和2^n-1之间的数字，其中n是使2^n-1大于或等于m的最小值。然后，只需在a上进行调整，您就可以了。

假设你得到的范围是20，30。那里有11个数字，从20到30 (含)。11大于8 (2^3)，但小于16 (2^4)，因此需要4位。使用bin()生成四位b0、b1、b2和b3。把它们放在一起作为x = b3 * 2^3 + b2 * 2^2 + b1 * 2 + b0。您将得到一个结果，x，介于0到15之间。如果x> 11，则生成另外4位。当x <= 11时，您的答案是x + 20。

帮助，但没有密码：

• 您可以轻松地将范围0、2 ** n转换为a，a+2 ** n。
• 你可以很容易地从0,2**n-1中产生一个相等的概率。
• 如果您需要的数字不是2的幂，只需生成一个最多2 ** n的数字，如果它超过所需的数，则重新滚动。

减去数字，计算出你的范围：

Decimal: 20 - 10 = 10
Binary : 10100 - 01010 = 1010

计算出表示以下内容所需的位数：4。

对于其中的每一个，生成一个随机的1或0：

num_bits = 4
rand[num_bits]
for (x = 0; x < num_bits; ++x)
  rand[x] = bin()

假设在此之后是rand[] = [0,1,0,0]。将此数字添加到范围的开始。

Binary: 1010 + 0100 = 1110
Decimal: 10 + 4 = 14