使用RDRAND指令生成无偏差指定范围随机数的方法探究

原示例的无偏差性确认 #

那两个示例确实是无偏差的：

• 生成[0,255]的随机数：rdrand ax取16位随机数，movzx r12,al只保留低8位，255是2^8-1，正好覆盖所有8位可能的取值，每个数的出现概率完全均等。
• 生成[0,1]的随机数：rdrand r8生成64位随机数，and r8,1提取最低位，RDRAND输出的每一位都是独立均匀的，所以0和1的概率各占50%，无偏差。

[0,N]范围的偏差问题 #

当N+1不是2的幂次时（比如你说的N=512，N+1=513，不是2的整数次幂），直接用掩码截断的方式会引入偏差。比如取10位得到0-1023，要是直接把513-1023的数强行映射到0-512，会导致部分数被选中的概率更高，破坏均匀性。

你的拒绝采样代码点评 #

你写的这段拒绝采样代码逻辑是对的，确实能生成无偏差的[0,512]随机数：

1. 用rdrand eax生成32位随机数，jnc retry0处理生成失败的情况（RDRAND的CF位为0表示生成失败）；
2. and eax,1023把范围缩小到0-1023（10位），减少后续判断的范围；
3. 只要生成的数大于512就重试，留下的0-512每个数的出现概率完全均等——因为每次生成的随机数都是均匀分布的，拒绝不符合条件的数后，剩余样本的分布依然均匀。

可以做一点小优化，去掉多余的内存操作，同时让判断更直观：

; 生成[0,512]的无偏差随机数，存入num变量
retry0:
    rdrand eax
    jnc retry0          ; 生成失败则重试
    cmp eax, 513        ; 判断是否超出[0,512]范围
    jae retry0          ; 大于等于513则重新生成
    mov [num], eax

核心结论 #

• 当目标范围的上限+1是2的幂次时，直接用掩码截断低N位就能得到无偏差随机数；
• 非2的幂次范围，必须用拒绝采样（生成随机数→判断是否在目标范围→不在就重试）才能保证无偏差，你的代码思路完全正确。

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