随机数生成题，利用小的随机数生成大的随机数

如题已经有一个黑盒函数 会生成均匀分布的随机数 0,1

需要构造一个随机函数，生成0~N之间均匀分布的随机数

利用0,1构造一0~2^K之间的随机数 （K = ceiling(log(N))）

如果生成的随机数大于N，则重新计算。否则返回此随机数。结果是均匀分布的。

代码如下：

#include "../Lib/randomize.h"
#include <iostream>
#include <map>

int rand01()
{
    return RNG::getInstance().getInteger() % 2;
}

#define N (10)

int random(int num)
{
    int result = 0;
    int upperbound = 1;
    while (upperbound < (num + 1))
            upperbound *= 2;
    do
    {
        result = 0;
        int nBound = upperbound;
        while ((nBound /= 2) > 0)
            result += nBound * rand01();
    } while (result > num);
    return result;
}

int main(int argc, char **argv)
{
    printf("Randomize test 1,000,000 of rand01 result:\n");

    long long  resultN[N + 1] = {0};
    for (long long i = 0; i < 1000000; ++i)
        ++resultN[random(N)];

    for (int i = 0; i <= N; ++i)
        printf("%d is : %ld\n", i, resultN[i]);
    return 0;
}

运行结果：

这里用到了一个自己封装的C++随机数生成类参考以下地址：

https://github/sesiria/Algs/blob/master/Lib/randomize.h