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

Question

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

给定一个随机返回0或1的函数BinaryRandom((，创建一个函数int MyRandom(int(，它创建一个小于或等于使用BinaryRandom((的给定输入。

由于我是GeeksForGeeks的每日堆栈溢出用户，我记得GeeksFerGeeks上也有类似的问题，请参阅下面的链接

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

唯一的区别是GeeksForGeeks的范围是0-6，在我的情况下范围是<N(N为输入整数(。

并且上述解决方案是使用以下链接从SO导出的

通过掷硬币创建一个随机数生成器。

作为算法的初学者，我发现上面的内容很难理解。有人能为上述问题提出一个简单的解决方案吗？还是简单地理解一下？

Answer 1

给定一个返回0或1的函数BinaryRandom((
创建一个函数intMyRandom(int)，该函数创建一个小于或等于给定输入的随机数

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的操作来避免对结果产生偏差。

Answer 2

基于chux的答案，这里有一个简单的实现：

int MyRandom(int max) {
for (;;) {
int r = 0;
for (m = max; m > 0; m >>= 1) {
r += r + BinaryRandom();
}
if (r <= max || max < 0)
return r;
}
}