给定一个随机位函数生成一个随机整数

Question

假设给定一个 int randBit() 函数，它 returns 均匀分布，0 或 1。

写一个 randNumber(int max) 函数。

这是我的实现，但我不能prove/disprove认为它是正确的。

    // max number of bits
    int i = (int)Math.floor(Math.log(max) / Math.log(2)) + 1;

    int ret = randBit();
    while (i-- > 0) {
        ret = ret << 1 | randBit();
    }

    return ret;

我的基本想法是

找出数字中存在的位数
然后通过连续连接 LSB 直到满足位长来生成数字

Answer 1

我认为用随机位填充整数的方法是正确的方法。但是，由于您的算法仅在 max 是 2 的幂并且在循环中关闭 1 时才有效，因此我建议进行此修改：

// max number of bits
int i = (int)Math.floor(Math.log(max) / Math.log(2)) + 1;

int rnd = 0;
int mask = 1;

while (i-- > 0) {
    rnd = rnd << 1 | randBit();
    mask <<= 1;  // or: mask *= 2
}
double q = (double)rnd / mask; // range is [0, 1)
return (int)((max + 1) * q);

我们来看看这个：

i 将始终等于 max 占用的位数。循环完成后，rnd 将包含用 0 或 1 随机填充的位数，而 mask-1 将包含用 1 填充的位数。因此可以安全地假设 rnd 和 mask-1 的商均匀分布在 0 和 1 之间。这与 max 相乘将产生 0 和 max 之间的结果，也均匀分布，就 floating/real 值而言。

现在这个结果必须映射到整数，当然你希望它们也均匀分布。这里唯一的问题是 1。如果 rnd 和 mask-1 的商恰好为 1，那么在缩放到所需的结果范围时会有一个边缘情况会导致麻烦：会有 0 .. max-1 值均匀分布，但 max 将是一个罕见的例外。

为了处理这种情况，商必须建立在 0 到 1 的范围内，但 1 不包含。这是通过 rnd / mask 实现的。通过乘以 max+1 并转换为 int.

，可以轻松地将此范围映射到均匀分布的整数 0 .. max

给定一个随机位函数生成一个随机整数

generate a random int given a random bit function

random

binary

numbers

bit-manipulation

bit