为什么此随机值的分布为 25/75 而不是 50/50？

random java bit-manipulation double probability

2022-08-31 08:02:03

编辑：所以基本上我试图写的是一个1位哈希。double

我想将 a 映射到或具有 50/50 的几率。为此，我编写了选择一些随机数的代码（仅作为一个例子，我想在具有规律性的数据上使用它，并且仍然得到50/50的结果），检查它们的最后一个位，如果它是1，或者它是0，则递增。doubletruefalseyn

但是，此代码不断导致 25% 和 75% 。为什么不是50/50？为什么会有这样一个奇怪但直截了当的（1/3）分布？yn

public class DoubleToBoolean {
    @Test
    public void test() {

        int y = 0;
        int n = 0;
        Random r = new Random();
        for (int i = 0; i < 1000000; i++) {
            double randomValue = r.nextDouble();
            long lastBit = Double.doubleToLongBits(randomValue) & 1;
            if (lastBit == 1) {
                y++;
            } else {
                n++;
            }
        }
        System.out.println(y + " " + n);
    }
}

输出示例：

250167 749833

答案 1

因为 nextDouble 的工作方式如下：（source)

public double nextDouble()
{
    return (((long) next(26) << 27) + next(27)) / (double) (1L << 53);
}

next(x)使随机位。x

为什么这很重要呢？因为第一部分（在除法之前）生成的数字大约有一半小于，因此它们的有效位数不能完全填充它可以填充的53位，这意味着有效数的最低有效位对于这些位始终为零。1L << 52

由于这引起了人们的广泛关注，这里有一些关于Java（和许多其他语言）中a的真正样子以及为什么它在这个问题上很重要的额外解释。double

基本上，看起来像这样：（来源double)

double layout

在此图片中不可见的一个非常重要的细节是，数字被“归一化”¹，使得53位分数以1开头（通过选择指数），然后省略1。这就是为什么图片显示分数（有效位数）为52位，但实际上其中有53位。

规范化意味着，如果在代码中设置了第 53 位，则该位是隐式前导 1，它将消失，其他 52 位将逐字复制到结果的有效位数。但是，如果未设置该位，则必须将其余位向左移动，直到其成为设置。nextDoubledouble

平均而言，生成的数字中有一半属于有效数根本没有向左移动的情况（大约一半的数字将0作为其最低有效位），而另一半则至少移位1（或完全为零），因此它们的最低有效位始终为0。

1：并非总是如此，显然不能为零完成，它没有最高的1。这些数字被称为非正态或非正态数，请参阅wikipedia：非正态数。

答案 2

从文档中：

方法 nextDouble 由 Random 类实现，就好像由：
public double nextDouble() {
  return (((long)next(26) << 27) + next(27))
      / (double)(1L << 53);
}

但它也声明了以下内容（强调我的）：

[在Java的早期版本中，结果被错误地计算为：
 return (((long)next(27) << 27) + next(27))
     / (double)(1L << 54);
这似乎是等价的，如果不是更好的话，但实际上由于浮点数四舍五入的偏差，它引入了一个很大的不均匀性：有效数的低阶位为0的可能性是1的三倍！这种不统一在实践中可能并不重要，但我们力求完美。

这个说明至少从Java 5开始就存在了（Java的文档<= 1.4在登录墙后面，懒得检查）。这很有趣，因为即使在Java 8中，这个问题显然仍然存在。也许“固定”版本从未经过测试？