c++ - 生成均匀分布的随机比特集的方法

Question

如何生成长度为 8 倍数(对应标准数据类型)的位集，其中每个位为 0 或 1 的概率相等？

Answer 1

以下作品。

• 选择具有良好统计特性的 PRNG
• 播种好
• 生成包含范围内的整数，包括整数类型的最小值和最大值。
• 由于整数在其整个范围内均匀分布，因此每个位表示的概率必须相等。由于所有位表示都存在，因此每个位都同样可以打开或关闭。

以下代码完成此操作:

#include <cstdint>
#include <iostream>
#include <random>
#include <algorithm>
#include <functional>
#include <bitset>

//Generate the goodness
template<class T>
T uniform_bits(std::mt19937& g){
  std::uniform_int_distribution<T> dist(std::numeric_limits<T>::lowest(),std::numeric_limits<T>::max());
  return dist( g );
}

int main(){
  //std::default_random_engine can be anything, including an engine with short
  //periods and bad statistical properties. Rather than cross my finers and pray
  //that it'll somehow be okay, I'm going to rely on an engine whose strengths
  //and weaknesses I know.
  std::mt19937 engine;

  //You'll see a lot of people write `engine.seed(std::random_device{}())`. This
  //is bad. The Mersenne Twister has an internal state of 624 bytes. A single
  //call to std::random_device() will give us 4 bytes: woefully inadequate. The
  //following method should be slightly better, though, sadly,
  //std::random_device may still return deterministic, poorly distributed
  //numbers.
  std::uint_fast32_t seed_data[std::mt19937::state_size];
  std::random_device r;
  std::generate_n(seed_data, std::mt19937::state_size, std::ref(r));
  std::seed_seq q(std::begin(seed_data), std::end(seed_data));
  engine.seed(q);

  //Use bitset to print the numbers for analysis
  for(int i=0;i<50000;i++)
    std::cout<<std::bitset<64>(uniform_bits<uint64_t>(engine))<<std::endl;

  return 0;
}

我们可以通过编译(g++ -O3 test.cpp)并使用以下命令进行一些统计来测试输出:

./a.out | sed -E 's/(.)/ \1/g' | sed 's/^ //' | numsum -c | tr " " "\n" | awk '{print $1/25000}' | tr "\n" " "

结果是:

1.00368 1.00788 1.00416 1.0036 0.99224 1.00632 1.00532 0.99336 0.99768 0.99952 0.99424 1.00276 1.00272 0.99636 0.99728 0.99524 0.99464 0.99424 0.99644 1.0076 0.99548 0.99732 1.00348 1.00268 1.00656 0.99748 0.99404 0.99888 0.99832 0.99204 0.99832 1.00196 1.005 0.99796 1.00612 1.00112 0.997 0.99988 0.99396 0.9946 1.00032 0.99824 1.00196 1.00612 0.99372 1.00064 0.99848 1.00008 0.99848 0.9914 1.00008 1.00416 0.99716 1.00868 0.993 1.00468 0.99908 1.003 1.00384 1.00296 1.0034 0.99264 1 1.00036

由于所有值都“接近”一个，因此我们得出结论，我们的使命已完成。