从一系列使用按位＆代替模运算的随机样本的整数(Using bitwise & instead of

我需要随机整数的在间隔的均匀分布采样[LB,UB]在C ++中。要做到这一点，我开始一个“好” RN发生器，均匀随机地采样的64位整数（从数字食谱第三版）; 让我们把它int64()

使用mod运算符，我可以从整数采样[LB,UB]由：

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

使用Mod运算符的唯一问题是整数除法的缓慢。于是，我又试图建议的方法在这里，它是：

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

按位＆方法为约3倍的速度。这是巨大的我，因为我用C模拟一个++需要随机抽样约20百万个整数。

但有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()函数不能在所期望的范围同等地分配。这可能是偏见太小，影响特别是你的模拟，但糟糕的随机数生成器在过去的破碎随机模拟，并会再次这样做。

如果你想在任意范围内的均匀随机数的分布，然后使用std::uniform_int_distribution从C ++ 11，或类升压同名。

这种运作良好，如果距离差（ UB-LB ）为2 ⁿ -1，但不会例如2 ^N在所有的工作好，如果。

这两者是等价仅当间隔的大小是二的幂。一般而言Y％的x和y＆（X-1）是不一样的。

例如x％5产生从0到4个数字（或至-4，为负x），但X和4产生0或4，从未1，2，或3，因为如何按位运算符工作...

文章来源: Using bitwise & instead of modulus operator to randomly sample integers from a range