c++ - 使用按位 & 而不是模数运算符从一个范围内随机抽取整数

Question

我需要在 C++ 中从 [LB,UB] 区间内均匀分布的整数中随机抽样。为此，我从一个“好的”RN 生成器(来自 Numerical Recipes 第 3 版)开始，它均匀地随机采样 64 位整数；我们称它为 int64()。

使用 mod 运算符，我可以通过以下方式从 [LB,UB] 中的整数中采样:

LB+int64()%(UB-LB+1);

使用 mod 运算符的唯一问题是整数除法的速度很慢。因此，我随后尝试了建议的方法 here ，即:

LB + (int64()&(UB-LB))

按位 & 方法大约快 3 倍。这对我来说意义重大，因为我在 C++ 中的一个模拟需要随机抽取大约 2000 万个整数。

但是有 1 个大问题。当我分析使用按位 & 方法采样的整数时，它们似乎并未均匀分布在区间 [LB,UB] 上。整数确实是从 [LB,UB] 中采样的，但仅是从该范围内的偶数整数中采样的。例如，这是使用按位 & 方法从 [20,50] 采样的 5000 个整数的直方图:

相比之下，这是使用 mod 运算符方法时类似直方图的样子，当然效果很好:

我的按位 & 方法有什么问题？有没有办法修改它，以便在定义的间隔内对偶数和奇数进行采样？

Answer 1

按位 & 运算符查看其操作数的每一对对应位，仅使用这两个位执行 and，并将结果放入对应的位结果。

所以，如果UB-LB的最后一位是0，那么结果的最后一位就是0。也就是说，如果 UB-LB 是偶数，那么每个输出都是偶数。

&不符合目的，除非UB-LB+1是2的幂。如果你想求一个模数，那么没有通用的捷径: 编译器已经以它知道的最快方式实现了 %。

请注意，我说的不是通用 快捷方式。对于在编译时已知的 UB-LB 的特定值，可以有更快的方法。如果你能以某种方式安排 UB 和 LB 具有编译器可以在编译时计算的值，那么它会在你编写 %.

顺便说一下，使用 % 实际上不会在范围内产生均匀分布的整数，除非范围的大小是 2 的幂。否则肯定会有轻微的偏向某些值，因为您的 int64() 函数的范围不能在所需范围内平均分配。可能是偏差太小而不会特别影响您的模拟，但糟糕的随机数生成器过去已经破坏了随机模拟，并且会再次这样做。

如果您想要在任意范围内均匀分布随机数，请使用 C++11 中的 std::uniform_int_distribution，或 Boost 中的同名类。