关于arc4random_uniform与PCG无偏均匀分布算法中-bound%bound取值及循环逻辑的技术问询

这是个非常好的问题，涉及到无符号整数运算特性和均匀随机数生成的核心细节，我们一步步拆解来看：

1. -bound % bound的结果并非始终为0 #

只有当bound是2的整数次幂时，这个表达式的结果才是0；其他情况下，它的结果等于2^N % bound（其中N是无符号整数的位数，比如32位或64位）。

背后的运算逻辑： #

在C语言中，无符号整数没有负数的概念，当你对无符号类型变量使用-运算符时，会触发补码转换规则：-bound等价于UINT{N}_MAX + 1 - bound（比如uint32_t的UINT32_MAX是0xffffffff，所以-bound就是0x100000000 - bound，也就是2^32 - bound）。

根据模运算的基本规则：

(a - b) % b = (a % b) - (b % b) = a % b - 0 = a % b

代入a=2^N、b=bound，就得到：

(2^N - bound) % bound = 2^N % bound

而2^N % bound只有当bound是2的幂时才为0（因为2^N是bound的整数倍），否则结果是一个介于1到bound-1之间的整数。

举个实际例子：假设bound=3（32位无符号），2^32=4294967296，4294967296%3=1，那么-3 % 3的结果就是1，而非0。

2. 为什么要用这个表达式计算阈值？ #

这个阈值（代码里的min或threshold）的本质是2^N除以bound的余数，它的核心作用是解决「直接取模导致的概率不均问题」：

如果直接对0~2^N-1的随机数执行r % bound，当2^{N不是bound的整数倍时，0到`min-1`这些数被选中的概率会比其他数略高（比如2}N=10，bound=3，2^N%3=1，那么0会出现4次，1和2各出现3次）。

过滤掉小于min的随机数后，剩下的随机数范围是min ~ 2^N-1，这个范围的长度是2^N - min，而因为min=2^N%bound，所以2^N - min刚好是bound的整数倍。此时再执行r%bound，每个结果的出现次数完全一致，实现了真正的无偏均匀分布。

3. 为什么需要循环与条件判断？ #

循环的作用就是丢弃不符合均匀分布要求的随机数，直到拿到落在有效范围内的随机数。虽然理论上这个循环可能无限执行，但实际上：

• 最坏情况下，每次重试成功的概率也大于0.5（比如当bound=2^(N-1)+1时，有效范围占总范围的比例约为50%）；
• 绝大多数场景下，成功概率远高于50%，循环几乎不会执行第二次，对性能的影响可以忽略不计。

另外补充一下Apple版本的实现：它本质和OpenBSD/PCG的逻辑完全一致，只是在32位系统上用了不同的方式计算2^32%bound（避免64位运算），最终得到的min值和-upper_bound%upper_bound的结果是完全相同的。

内容的提问来源于stack exchange，提问作者João Pires