如何高效生成无连续3个置位比特的无偏64位随机整数？

假设存在快速且无偏的输入PRNG，有没有高效方法生成无连续3个置位比特的无偏64位随机整数？可以接受浪费输入源的比特。

已尝试的低效/有偏方法 #

朴素拒绝采样 #

不断生成64位随机数，直到得到符合要求的结果，但效率极低，平均要迭代约187次：

uint64_t r;
do {
    r = get_rand_64();
} while (r & (r >> 1) & (r >> 2));

位串行生成法 #

逐位构建结果，但不仅速度慢（全程串行计算），还存在偏差：以3位整数为例，合法值共7个，0b011的理论概率应为1/7，但实际生成概率是1/8：

bool p2 = get_rand_bit();
bool p1 = get_rand_bit();
uint64_t r = (p1 << 1) | p2;
for (int i = 2; i < 64; i++) {
    bool p0 = (p1 && p2)? false : get_rand_bit();
    r |= p0 << i;
    p2 = p1;
    p1 = p0;
}

高效无偏的解决方案 #

方案1：分组并行生成（基于转移表） #

把64位拆成多个小段（比如每4位一组），提前计算合法的段组合和段间转移规则，批量用PRNG选段，大幅提升并行度：

1. 预计算n位（比如n=4）的所有合法序列：4位里排除0b0111、0b1110、0b1111，共13个合法值。
2. 预做转移表：记录前一段的末尾2位（因为要避免和下一段开头凑成连续3个1）对应的所有合法下一段。比如前一段末尾是11，下一段开头不能是1，所以只选开头为0的合法段。
3. 生成时，先随机选第一段，然后根据前一段的末尾两位，从转移表的对应列表里随机选下一段，拼起来直到凑够64位。
   这种方法每个合法序列被选中的概率完全匹配其在整体合法空间中的占比，无偏且速度快。

方案2：分块优化的拒绝采样 #

不用直接生成64位再拒绝，拆成小块（比如每5位一块）处理，把拒绝概率分摊到小块上：

1. 预算每个5位块的合法值：5位里排除所有包含连续3个1的情况，共29个合法值（合法率约90%）。
2. 生成第一个块后，记录它的末尾两位；后续每个块生成时，先过滤掉会和前一段末尾凑出连续3个1的候选值，再随机选合法值拼接。
   每个小块的拒绝概率极低，整体效率比全64位拒绝采样高几十倍。

方案3：索引映射生成法 #

利用合法序列数量的斐波那契递推特性：设f(n)为n位合法序列数，f(n)=f(n-1)+f(n-2)+f(n-3)（初始值f(1)=2，f(2)=4，f(3)=7）。64位的合法序列数f(64)是确定值，我们把PRNG生成的数映射到合法索引再解码：

1. 用PRNG生成足够比特组成大整数，对f(64)取模得到索引x——如果生成的数≥f(64)就丢弃重生成，这一步平均约4.3次就能得到有效索引，浪费的比特很少。
2. 从最高位到最低位递推确定每一位：比如当前剩余可选序列数是f(k)，若x < f(k-1)就把当前位设为0，否则设为1并调整x，同时结合前两位的状态确保不会出现连续3个1。
   提前预计算好f(1)到f(64)的数组，递推过程可以快速完成，完全无偏且效率高。

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