老黄、老银和老阳共事宇宙中心某互联网企业H，并且同在一个由校招新生组成的Team里。刚走出校园的他们，对自己去年在校招这场演技大比拼中的表现意犹未尽，因此常会拿一些没什么实际意义的技术问题大谈特谈。

这次是午饭后的扯皮时间，这几个人就吸着免费的明胶酸奶，从一些概率问题讨论到了随机数发生器上……

黄：像去年（校招），面试官就很喜欢问这种题目：给定一个[0, M)的均匀分布随机整数发生器（以下简称RNG），设计一个[0, N)的整数的均匀分布RNG。

阳：我被问的时候不知道怎么做，问我的人就得意的告诉我用——M进制。

黄：现实中RNG一般输出的是什么呢？

阳：我觉得最基本的应该是以bit或者byte为单位输出的。毕竟RNG就是一连串的位操作，比如像那个什么Twister算法（梅森旋转算法）这种，所以可见M必定是2的幂。

黄：如果是这样，我会先用RNG产生足够的随机位数存下N，然后截取小于N的值返回就行了。

阳：……我想如果从这个RNG出发，它只有类似于nextByte的方法返回一个随机byte，以此实现一个生成指定范围的int、long、float、double的RNG……

黄：int和long很简单啊，就我刚才说的方法

老黄在白板上写下pseudo code

int nextInt(int min, int max) {    int range = max - min;    while (true) {        int random = 0;        int ceiling = 1;        for (int i = 0; i < 4; ++i) {            random = (random << 8) | rng.nextByte();            ceiling = ceiling << 8;            if (ceiling >= range)                break;        }        if (random < 0 || random >= range)            continue;        return min + random;    }}

（看上去不错，首先把[a, b)的问题转化为[0, b-a)；生成随机数时，只产生了必要的byte数；最后考虑了负数情况）

阳：……貌似有两个问题：1）range有可能溢出int的范围；2）在极端情况下，这个RNG生成一个随机数平均要执行200多次nextByte。比方说给定随机数范围[0, 1)吧，其实只有0是可取的，你这边虽然只调用一次nextByte，但是值域是[0, 256)，取到0的概率是1/256啊，这是不是太heavy了？……哦，还有一个问题，3）ceiling只要算一次就行了吧？而你这边生成失败就会重算。

黄：第一个问题range可以用long替代。第二个问题么……

阳：那nextLong怎么办？

黄：……有没有128位的整型？

阳：…………我想没有……你可以造一个…………算了，我们限定所有的范围都必须是非负整数吧，那第二个问题呢？

黄：（思考一分钟）……我改变一下设计。

int nextInt(int min, int max) {    int range = max - min;    int times = 0;    int ceiling = 1;    for (; times < 4; ++times) {        if (ceiling >= range)            break;        ceiling = (ceiling << 8);    }    if (ceiling < 0)        ceiling = MAX_INT;    ceiling = ceiling - ceiling % range;    while (true) {        int random = 0;        for (int i = 0; i < times; ++i)            random = (random << 8) | rng.nextByte();        if (random < 0 || random >= ceiling)            continue;        return min + random % range;    }}

黄：现在我只需执行一次就能获得最小byte数times，然后ceiling现在是小于等于RNG产生值域的最大值的range的倍数中最大的那个……

阳：我明白，你把[0, ceiling)上的均匀分布折叠到[0, range)上，只要ceiling是range的倍数，均匀性就能保持，ceiling扩大了RNG输出的有效值域范围，也就降低了重复试验的次数。

黄：对，换而言之，重复试验的概率现在最差情况是1/2，就是当range刚好超过RNG输出值域一半的时候，这时候range本身就是ceiling……但这里面还有一个问题：当range非常大，需要四次nextByte的时候，我有1/2概率会得到负数，加上刚才说的情况，于是我会有3/4的概率要抛弃生成的byte，而这正好又发生在nextByte调用次数最多的一类里面。

阳：可以用abs？

黄：对，但是要排除掉MIN_INT，否则会溢出嘛…………（沉思片刻）………不对，不行。

阳：为什么？

黄：你看，排除掉MIN_INT我得到的是[-MAX_INT, MAX_INT]上的均匀分布？

阳：对。

黄：然后我用abs把负数对折到正数上？

阳：…………我明白了，是0，对折后，0取到的概率是其他正整数的1/2，这就破坏均匀性了。

黄：是的…………其实我们只要这样，把负数的最高位置零就行了，这建立了负数到非负数的一一映射。

阳：MIN_INT被映射到了0，不错。但均匀性能保证么，比如虽然是一一映射，但是把松散的区域映射到密集的区域就不一定有效吧？

黄：应该不会，首先nextByte是无符号的，所以通过它生成的4字节随机数是无符号整型上的均匀分布，uint上大于MAX_INT的部分也就是[MIN_INT, -1]并且顺序也是一样的，所以我们把负数高位1抹去，也就是一种折叠，这种操作是证明保持均匀性的。相比较abs反而不合理，因为它将[MIN_INT+1, -1]上分布先逆序，再叠加到正整数上，我不确定这种操作是否合理。

阳：有道理。

黄：所以代码这么写。

int nextInt(int min, int max) {    int range = max - min;    int times = 1;    int ceiling = 1;    for (; times < 4; ++times) {        if (ceiling >= range)            break;        ceiling = (ceiling << 8);    }    if (ceiling < 0)        ceiling = MAX_INT;    ceiling = ceiling - ceiling % range;    while (true) {        int random = 0;        for (int i = 0; i < times; ++i)            random = (random << 8) | rng.nextByte();        random = random & MAX_INT;        if (random < ceiling)            return min + random % range;    }}

阳：现在最坏情况下期望2次可以得到随机数。

黄：其实现在我觉得没必要获得times，每次都生成一个4字节随机数也可以，毕竟省掉了计算times的一次循坏。

int nextInt() {    int random = 0;    for (int i = 0; i < 4; ++i)        random = (random << 8) | rng.nextByte();    return random & MAX_INT;}int nextInt(int max) {    int ceiling = MAX_INT - MAX_INT % max;    while (true) {        int random = nextInt();        if (random < ceiling)            return min + random % range;    }}int nextInt(int min, int max) {    return min + nextInt(max - min);}

黄：写成这样可读性更好不是么，也能丰富API。

阳：现在这样实现，long的写法也一模一样了，不错。下面看看浮点数怎么实现。

银：你们可以看看apache.commons.lang模块啊，人家的……好像叫RandomUtils吧，什么都有。可以学学别人的实现。

（未完）

一个随机数发生器（一）