生成随机的64位整数

Question

我需要你的帮助，请给我一些建议。从《编程珠玑》中，我知道要生成一个30位的随机整数，我们应该这样写：

RAND_MAX*rand()+rand()

但是，如果我想要生成64位的随机整数，而不是30位的，我该怎么办呢？如果我先乘以两个30位的整数，然后再乘以4位的整数，那么这种方法效率非常低下。那么我应该使用什么样的方法呢？我现在正在使用popcount_1不同的方法来生成64位的随机整数，并且我想在随机整数上进行测试（我也在测量每个方法完成任务所需的时间）。

- user466534

---

你也可以进行移位和加法运算。 - duedl0r

Answer 1

首先，我对您在30位整数的解决方案表示怀疑。 RAND_MAX本身可能是31位值，RAND_MAX * rand() + rand()可能会溢出，产生未定义的行为（实际上为负值）。

如果您需要一个大于RAND_MAX保证最小值的值，或者任何比RAND_MAX显着小的值，唯一的解决方案将是使用连续调用rand()并组合这些值，但您需要仔细处理，并验证结果。（大多数rand()实现使用线性同余生成器，虽然对某些任务足够，但在这种情况下并不特别好。）无论如何，类似以下内容：

unsigned 
rand256()
{
    static unsigned const limit = RAND_MAX - RAND_MAX % 256;
    unsigned result = rand();
    while ( result >= limit ) {
        result = rand();
    }
    return result % 256;
}

unsigned long long
rand64bits()
{
    unsigned long long results = 0ULL;
    for ( int count = 8; count > 0; -- count ) {
        results = 256U * results + rand256();
    }
    return results;
}

（ rand256 中的代码旨在消除将 RAND_MAX 值映射到256个值时不可避免的偏差。）

- James Kanze

---

如何控制此代码的精度。比如我想生成61位的随机数而不是64位。我认为，如果我从7开始计数而不是8，我会得到一个56位的随机数。我是正确的吗？ - arunmoezhi

如果你能生成64个随机比特，那么你可以通过生成64个比特并且舍弃3个来生成61个比特；例如，通过屏蔽掉前三个比特。 - James Kanze

谢谢。你的解决方案看起来不错。但如果您能添加一些说明，那会更有帮助。我花了一些时间才理解你在做什么。 - arunmoezhi

Answer 2

这可能是一种解决方案，无需进行乘法运算：

r30 = RAND_MAX*rand()+rand()
s30 = RAND_MAX*rand()+rand()
t4  = rand() & 0xf

res = (r30 << 34) + (s30 << 4) + t4

- duedl0r

---

假设RAND_MAX是1<<15。如果你确实这样假设，为什么不使用以下表达式：rand() + rand() << 15 + rand() << 30 + rand() << 45 + (rand() & 0xf) << 60？完全没有乘法运算。 - MSalters

为什么不直接使用以下代码:return ((unsigned long long)rand() << 48) | ((unsigned long long)rand() << 32) | ((unsigned long long)rand() << 16) | ((unsigned long long)rand() & 0xffff);? 这里没有任何乘法，只有移位。 - user152949

虽然可以生成64位随机数，但是我认为生成的随机数分辨率不能超过随机数种子。 - Cris

你说“不用乘法”，但是实际上还是有乘法的。而且这种方法并不能保证均匀分布（例如，r30 等于 RAND_MAX 的方式有两种）。当然，未声明的假设 RAND_MAX == 1<<15 在许多实现中都不成立。 - interjay

Answer 3

如果 boost是一个选项，您可以使用 boost random。

- Andrea Bergia

---

你确定它可以生成64位吗？你的链接说明了另外一种情况："mt19937在范围[0，2^32-1]内生成整数。" - duedl0r

看一下各种生成器（http://www.boost.org/doc/libs/1_47_0/doc/html/boost_random/reference.html#boost_random.reference.generators），例如`ranlux64_3`。 - Andrea Bergia

如果它确实在整个区间[0, 2^32-1]上生成了一个好的随机值，那么将两个调用组合以生成一个好的64位随机值应该是相当简单的。（当然，“好”的定义要足够宽松。基本生成器仍需要2^64或更长的周期，否则会有很多值无法生成。） - James Kanze

从统计学的角度来看，要生成所有值，您可能需要使用周期至少为2 ^ 64的生成器。从实际角度来看，对于大多数应用程序，具有移位/乘法的简单解决方案已经足够好了。 - Andrea Bergia

使用默认选择（mt19937），周期确实不是问题。 2^19937比宇宙的寿命还要长得多。 - MSalters

Answer 4

一个随机的64位整数实际上是将64个随机位解释为整数。

使用随机字节填充长度为8的字节数组（请参见此处），并将其解释为整数（请参见此处）。

- Rich O'Kelly

---

我怀疑大多数rand()函数的实现在这样做时可能不会产生特别均匀的分布。 - Flexo

Answer 5

一种通用解决方案：

template <unsigned long long I> struct log2 {
  static const int result = 1 + log2<I/2>::result;
};
template <> struct log2<1> {
  static const int result = 0;
};

template <typename UINT> UINT genrand() {
  UINT result = 0;
  int bits = std::numeric_limits<UINT>::digits;
  int rand_bits = log2<RAND_MAX>::result;
  while (bits > 0) {
    int r = rand();
    while (r >= (1<<rand_bits)) r = rand(); // Retry if too big.
    result <<= rand_bits;
    result += r;
    bits -= rand_bits;
  }
  return result;
}

使用：unsigned long long R = genrand<unsigned long long>();。 bits 计数器跟踪仍需的位数。

- MSalters

Answer 6

'返回一个介于0和RAND_MAX（包括0和RAND_MAX）之间的伪随机整数值。' - http://en.cppreference.com/w/cpp/numeric/random/rand

因此，您应该使用RAND_MAX + 1（就像逐位生成数字然后将其转换为十进制一样）而不是RAND_MAX。 这样，您可以在基数RAND_MAX + 1中生成具有一位、两位、三位等数字（可能带有前导零），并将它们转换为十进制并获得任意大的数字。

您获得的所有大于所需MAX_VALUE的内容都可以丢弃，仍然可以获得每个数字的1 /（MAX_VALUE + 1）概率。

请注意，这种方法可能需要一段时间，特别是如果您所需的MAX_VALUE远小于在丢弃不需要的数字之前可以获得的最大值，则使用此算法获取[0，MAX_VALUE]范围内的随机数的预期步骤数为：（MAX_OBTAINABLE_VALUE + 1）/（MAX_VALUE + 1）

- MciprianM