c - 使用可用的 binaryrandom(返回 0 或 1)函数生成整数随机数

Question

在最近的一次采访中，我遇到了以下问题

Given a function BinaryRandom() which returns 0 or 1 randomly, createa function int MyRandom(int) which creates a random number less orequal to the given input using BinaryRandom().

因为我是一个日常堆栈溢出和 GeeksForGeeks 用户，我记得在 GeeksForGeeks 上有类似的问题，请参见下面的链接

https://www.geeksforgeeks.org/implement-random-0-6-generator-using-the-given-random-0-1-generator/

唯一的区别是 GeeksForGeeks 的范围是 0-6，在我的例子中范围是 <=N(N 是输入整数)。

上述解决方案是使用以下链接从 SO 派生的

Creating a random number generator from a coin toss .

作为算法的初学者，我发现上面的内容很难理解。任何人都可以为上述问题提出一个简单的解决方案吗？或者给个简单的理解？

Answer 1

Given a function BinaryRandom() which returns 0 or 1
create a function int MyRandom(int) which creates a random number less or equal to the given input

int MyRandom(int max);

1. 查找 max 的位宽 --> bitwidth。也许计算右移直到 0。例如对于 max == 42，我们需要 6 位。

2. 通过调用 BinaryRandom() 生成随机数。例如。有 6 位，这将形成一个数字 [0...63]。

   int r = 0;
   // Double the value each iteration and add new bit.
   for (i = 0; i<bitwidth; i++) r = 2*r + BinaryRandom();  
   

3. 确保不超出范围:如果r > max，重复步骤2。

4. 返回r。

有一些方法(未显示)可以减少必须重做第 2 步的可能性，但我们希望通过执行 r_from_more_than_6_iterations%42 之类的操作来避免结果出现偏差。