生成随机位的最快方法

Question

如何快速生成大量（伪）随机比特？每个比特必须是独立的，并且以等概率为零或一。显然，我可以对其进行某些变化。

randbit=rand()%2;

但我觉得应该有更快的方法，每次调用随机数生成器时生成几个随机位数。理想情况下，我想获得一个整数或字符，其中每个二进制位都是随机且独立的，但也可以使用其他解决方案。

这个应用程序不涉及密码学，因此强大的随机性并不是主要因素，而速度和正确的分布是很重要的。

- dagw

---

你在寻找哪个发行版？对于发行版的正确性，你有多挑剔？如果你真的希望对于区间[1..n]中的数字x，P[x] = 1/n，那么即使你的应用程序不是加密相关的，你仍然需要一个好的随机数生成器。 - AnnaR

像 ((int)rand*rand)%2 这样的东西怎么样？ - C4d

可能是 https://dev59.com/cYLba4cB1Zd3GeqPb0Hu 的重复（那个问题更广泛，因为它还询问了非50:50分布的情况）。 - mxmlnkn

Answer 1

将随机数转换为二进制
为什么不获取一个数字（大小适当以获得所需的足够位数）然后将其转换为二进制。你实际上会从一个随机数中获得位，这意味着它们也是随机的。

0和1的概率也是50％，因为取所有介于0和某个2^n限制之间的数字，并计算零和一的数量相等> 这意味着零和一的概率是相同的。

关于速度
这可能非常快，因为只获取一个随机数与其中的位数相比更快。现在完全取决于您的二进制转换。

- Robert Koritnik

---

简短提示：二进制转换可以使用简单的位移循环实现：for ( i = 0; i < sizeof( randomNumber ) * 8; ++i ) { std::cout << ( randomNumber & 1U ); randimNumber >>= 1U; }，假设randomNumber是一个无符号整数。 - mxmlnkn

Answer 2

请看一下Boost.Random，特别是boost::uniform_int<>。

- avakar

Answer 3

如你所说，只需生成随机整数。

那么你就有了32位随机比特，每个比特都是等概率的1或0。

通过循环获取这些比特：

for (int i = 0; i < 32; i++)
{
  randomBit = (randomNum >> i) & 1
  ...
  // Do your thing
}

重复此步骤直到获得正确的比特数。

- Sani Huttunen

---

rand函数不能保证返回32位随机数，事实上在MSVC下，它只返回16位。 - avakar

当然，它是平台相关的，但原则不管在哪个平台上都是相同的。 - Sani Huttunen

它们真的是均匀分布的吗？我考虑过这个想法，但无法完全相信每个位都是均匀且独立分布的。 - dagw

这取决于位数的数量。在较小的子集中，您可能会发现偏斜的分布，但是集合越大，分布就会变得更加均匀。由于您特别想要大量的位数，因此这应该满足您的分布正确性要求。 - Sani Huttunen

常见的随机数生成器具有完全非随机的最低有效位（总是翻转）。 - MSalters

Answer 4

这是我用Java编码的一个非常快速的算法，基于George Marsaglia的XORShift算法：一次获取64位！

/**
 * State for random number generation
 */
private static volatile long state=xorShift64(System.nanoTime()|0xCAFEBABE);

/**
 * Gets a long random value
 * @return Random long value based on static state
 */
public static final long nextLong() {
    long a=state;
    state = xorShift64(a);
    return a;
}

/**
 * XORShift algorithm - credit to George Marsaglia!
 * @param a Initial state
 * @return new state
 */
public static final long xorShift64(long a) {
    a ^= (a << 21);
    a ^= (a >>> 35);
    a ^= (a << 4);
    return a;
}

- mikera

---

请注意：这个算法之所以如此快速，是因为它只使用了简单的位运算符，在一个已被证明（Marsaglia）可以生成“足够好”的伪随机序列的顺序中。这 不是 密码学上的强加密，但对于游戏、模拟等领域来说已经足够好了。 - mikera

Answer 5

SMP安全（即目前最快的方式）和好的位元

请注意使用 [ThreadStatic] 属性，此对象会自动处理新线程，无需锁定。这是确保高性能随机、SMP无锁的唯一方法。

http://blogs.msdn.com/pfxteam/archive/2009/02/19/9434171.aspx

- RandomNickName42

Answer 6

如果我没记错的话，对于大多数伪随机数生成器来说，最不显著的位通常具有“较少随机”的分布，因此如果您担心分布，使用模数和/或生成的数字中的每个位将是不好的选择。

（也许你至少应该谷歌一下Knuth说了什么...）

如果这成立（而且不知道您使用的算法是什么很难确定），只需使用每个生成的数字中的最高位即可。

http://en.wikipedia.org/wiki/Pseudo-random

- KarlP

Answer 7

#include <iostream>
#include <bitset>
#include <random>

int main()
{
    const size_t nrOfBits = 256;
    std::bitset<nrOfBits> randomBits;

    std::default_random_engine generator;
    std::uniform_real_distribution<float> distribution(0.0,1.0);

    float randNum;
    for(size_t i = 0; i < nrOfBits; i++)
    {
        randNum = distribution(generator);
        if(randNum < 0.5) {
            randNum = 0;
        } else {
            randNum = 1;
        }
        randomBits.set(i, randNum);
    }

    std::cout <<  "randomBits =\n" << randomBits << std::endl;
    return 0;
}

在我的测试中，这需要4.5886e-05秒，使用256位。

- Anno

---

我喜欢这个答案，因为它是唯一一个展示C++方法的，但我认为使用“伯努利分布（bernoulli_distribution）”可能会更好、更简单、更快速和更正确！ - mxmlnkn

@mxmlnkn 你为什么这样认为？ - Anno

因为你可以避免生成整个32位浮点数并进行比较，而是从高度优化的STL对象中获取一个随机位，并且还可以节省一些代码行，因为它可以简化为：std :: bernoulli_distribution bdist（0.5）; for（size_t i = 0; i <nrOfBits; i ++）randomBits.set（i，bdist（generator））; - mxmlnkn

Answer 8

你需要生成多少位数？如果不超过几百万，并且记住你不会用这个生成器进行密码学操作，那么我认为最快的方法是预先计算一组具有正确分布的大整数，将其转换为像这样的文本文件：

unsigned int numbers[] =
{
  0xABCDEF34, ...
};

然后将数组编译到您的程序中，逐个数字进行处理。

这样每次调用都可以获得32位(在32位处理器上)，生成时间最短，因为所有数字都提前生成，分布由您控制。当然，缺点是这些数字根本不是随机的，这取决于您使用PRNG的目的是否重要。

- ajanicij

Answer 9

您可以生成一个随机数，并不断向右移位并测试最低有效位来获取随机位，而不是执行模运算。

- Naveen

Answer 10

如果你只需要一次生成一个比特，可以尝试以下代码： bool coinToss() { return rand()&1; } 由于将%2替换为&1是等效的，因此这实际上是一种更快的生成比特的方法。

- user2146937