快速 C 随机布尔生成器

我对在 C 中生成快速随机布尔值（或等效的 Bernoulli(0.5) 随机变量）感兴趣。当然，如果有一个具有良好统计行为的快速随机生成器，那么“对随机 Bernoulli(0.5) 进行采样”的问题很容易已解决：样本x统一在(0,1)并返回1 if x<0.5, 0否则。

假设速度是最重要的，现在我有两个问题/考虑因素：

1. 许多随机双精度数生成器首先生成一个整数m统一在一定范围内[0,M]然后简单地返回除法m/M。仅检查是否会更快m < M/2 (here M/2是固定的，所以我们节省一个部门）

   2. 有没有更快的方法来做到这一点？最后，我们在这里要求更少的统计属性：我们可能仍然对很长一段时间感兴趣，但是，例如，我们不关心分布的均匀性（只要大约 50% 的分布）值位于范围的前半部分）。

Extracting say the last bit of a random number can wreak havoc as linear congruential generators can alternate between odd and even numbers¹. A scheme like clock() & 1 would also have ghastly correlation plains.

考虑一个基于 Donald Kunth 的快速而肮脏的生成器的解决方案：uint32_t I， 顺序

I = 1664525 * I + 1013904223;

and 2 * I < I是产生布尔图的条件。在这里我依赖于以下的环绕行为I这应该发生一半的时间，并且避免了潜在的昂贵的除法。

Testing I <= 0x7FFFFFFF不那么华丽并且可能更快，但是中点的硬编码并不完全令人满意。

¹ The generator I present here does.