C++中uniform_*_distribution类如何保证无抖动均匀分布？

你之前的判断是对的：只要输入的是符合标准要求的高质量均匀随机位生成器，uniform_int_distribution 就必须输出无偏差的等概率结果，C++标准对这个类的均匀性有强制要求，不会允许朴素范围映射带来的抖动问题。

你说的抖动来源非常明确：当随机源的原始输出值域长度，不是目标分布区间长度的整数倍时，直接用取模、整数乘除截断这类方式做范围映射，必然会导致部分输出值的出现概率略高于其他值——比如用输出范围为[0, 2^64-1]的mt19937_64生成[0,5]的整数，2^64除以6余4，直接gen()%6的话，0到3这四个值的出现概率会比4、5稍高，偏差虽然极小，但确实不满足严格均匀的要求。

所有合规标准库实现解决这个问题的方案都是拒绝采样，逻辑没有什么黑魔法，就是从根源上避开映射不均匀的问题：

• 先算目标区间长度：如果需要生成[a, b]范围内的整数，首先得到区间总长度range = b - a + 1。
• 划定可用值域范围：计算随机源输出值域里，能被range整除的最大连续块的上界，把值域末尾凑不齐整份range的小段划为废弃区间——这段的长度最多只有range-1，占整个随机源值域的比例极低。
• 循环采样过滤：每次调用随机源生成原始值，如果值落在废弃区间里就直接丢弃重抽，直到拿到落在可用区间内的值，再通过取模加偏移的方式映射到目标区间返回。

这个逻辑是完全无偏的：所有被保留的原始值出现概率完全相等，每个目标输出值对应的原始值数量也完全一致，自然不存在乘除映射带来的抖动。而且它的性能损失几乎可以忽略：当目标区间长度远小于随机源值域时，比如用mt19937_64生成32位以内范围的整数，单次采样触发重抽的概率不到2^-32，绝大多数场景下一次生成就能拿到可用值，不会有可感知的开销。

不要误以为标准库实现会偷懒用直接取模的写法，从C++11把随机数库纳入标准开始，uniform_int_distribution的严格均匀性就是强制要求，和你搭配使用的是mt19937_64还是其他合规随机引擎没有关系，只要随机源本身满足均匀位生成器的要求，输出就一定是无抖动的等概率结果。

内容的提问来源于stack exchange，提问作者Bonita Montero