c++ - RAND_MAX 和 UINT_MAX 之间的差异会有所不同吗？

Question

我的作业涉及生成 0 和 2^30 之间的随机整数。现在，在过去我们了解到 rand() 只返回小于 RAND_MAX 的整数，这小于 UINT_MAX，并且我们可以使用位移来填充 UINT_MAX 容量。从我所做的一些阅读中(这里，关于 SO)，我意识到如果这些数字的分布对我很重要，这可能不是一个好主意。话虽如此，我的教授已经指定了这种方法。

我的问题是，位移多少？ RAND_MAX 和 UINT_MAX 之间的差异是否始终存在一个安全常数来进行位移？或者是否需要进行一些初始探测以确定要移位的数字？我是否应该保持位移一点点并检查 UINT_MAX？

我问的原因是，UINT_MAX 被定义为至少是某个数字 (65535)，但在我的机器上 UINT_MAX更大(4294967295)。这让我担心我可能会在周末完成作业，到达学校后发现一切都不够顺利，无法提交。

谢谢!

引用资料:

我读过几个类似的问题，但无法从他们那里得到答案。

Is the value of RAND_MAX always (2^n)-1?

generating a random number within range 0 to n where n can be > RAND_MAX

实际上，上面的第二个问题让我怀疑这样做是否值得？

Answer 1

您的问题围绕着是否 RAND_MAX和 UINT_MAX他们之间有一点转变。这减少了是否 UINT_MAX 的问题和 RAND_MAX形式为 2^k - 1 . UINT_MAX几乎肯定会出现在任何基于二进制数系统的计算机上。如果sizeof(int)=32然后位 k=32 , 如果 sizeof(int)=64 bit然后 k=64等。现在我们可以考虑RAND_MAX .在大多数实现中，答案是 RAND_MAX几乎总是采用 2^k - 1 的形式.为什么？我们需要考虑 rand() 的大多数实现方式实际工作。

1. rand()通常使用线性同余生成器(参见 http://en.wikipedia.org/wiki/Linear_congruential_generator 或 Knuth“计算机程序员的艺术第 2 部分:半数值算法”)。基本上，随机数是一个带有 seed 的序列。

   x(k+1) = ( a x(k) + c ) % m

(即 C 库存储最后一次迭代的 x(k) 并且当您调用 rand() 时它返回 x(k+1) )

1. 要获得良好的质量，必须谨慎选择生成器的参数(a、c 和 m)。质量通常涉及序列重复自身之前的次数等。选择这些参数的一个紧张因素是使m成为可能。接近UINT_MAX尽可能避免浪费潜在的随机位。如果你研究发电机，通常正确的选择是 m略小于 UINT_MAX .您还需要制作 m一个素数。

2. 通常您需要 rand()尽可能快，所以你希望这些操作便宜。最便宜mod计算是一种形式 foo % (2^k - 1)因为它可以实现为 foo & (1<<k-1) .专供选择k你会得到一个梅森素数。

例如，一个常见的选择是 k=31产生素数 2^31-1 = 2147483647 .这是 32 位整数的典型选择，其中 UINT_MAX=2^32-1 = 4294967295 .对于 64 位数字，一个有 UINT_MAX=2^64-1=18446744073709551615 RAND_MAX 的选择是 2^61-1 = 2305843009213693951 .

总而言之，回答你的问题:在大多数实现中，你可以假设有一个简单的位移位，但是，没有真正的保证。至少你应该在你的程序初始化时做一个运行时测试。如果您使用 C++，更好的做法是使用 static_assert在编译时检测您的假设是否正确，如果不正确则无法编译。 Boost 有这样一个静态断言，最近批准的标准 C++11 也是如此……即可以做到(尽管编写 is_power_of_two_minus_one 的静态版本可能需要一些工作):

unsigned int myrand()
{
        static_assert(sizeof(int)==4,"sizeof(unsigned int) != 4");
        static_assert(is_power_of_two_minus_one(RAND_MAX),"RAND_MAX not a power of two minus one");
        static_assert(is_power_of_two_minus_one(UINT_MAX),"UINT_MAX not power of two minus one");
        unsigned int raw_rand=rand();
        // do your bit shift to adjust raw_rand
        return raw_rand;
}