如何生成均匀分布随机整数

前几天在水木上看到一个帖子，问如何用硬件实现一个0-56的随机数。这个问题初看起来不是很难，但是仔细想想还是蛮难实现的，尤其是希望能够尽量少的占用芯片面积时。

由这个问题，我想到另外一个稍微简单一些的问题，就是如何在程序中生成一个[0, N-1] 的随机整数。我们知道，C语言的标准库中有个 rand() 函数，这个函数可以生成[0, RAND_MAX] 之间的随机整数，并且理论上来说生成的随机整数是均匀分布的。我们就以此为基础来构造一个[0, N-1] 的均匀分布的随机整数。

要生成[0, N-1] 的随机整数，大多数的书上给出的方法是这样的：

(n & -n) == n

来判断 n 是否是 2 的整数次幂也很巧妙。要是让我来写，肯定写不出这么精彩的实现。

不过，这个代码的运行效率与我写的那个简单的代码基本相当，相比来说我那个代码还要更易读一些。