java - 为什么这个随机值的分布是 25/75 而不是 50/50？

Question

编辑:所以基本上我要写的是 double 的 1 位散列。

我想以 50/50 的几率将 double 映射到 true 或 false。为此，我编写了选择一些随机数的代码(仅作为示例，我想在有规律的数据上使用它并且仍然得到 50/50 的结果)，检查它们的最后一位并递增 y 如果是 1，或者 n 如果是 0。

但是，此代码不断导致 25% y 和 75% n。为什么不是 50/50？为什么会有如此奇怪但直截了当 (1/3) 的分布？

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

Answer 1

因为 nextDouble 是这样工作的:( source )

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

next(x)使x随机位。

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

---

由于受到了广泛关注，这里有一些关于 double 的额外解释。在 Java(和许多其他语言)中看起来确实如此，以及为什么它在这个问题中很重要。

基本上，double看起来像这样:(source)

在这张图片中看不到的一个非常重要的细节是数字被“标准化”¹ 使得 53 位小数以 1 开头(通过选择这样的指数)，即然后省略 1。这就是为什么图片显示分数(有效位)为 52 位，但实际上有 53 位。

规范化意味着如果在 nextDouble 的代码中第 53 位被设置，该位是隐含的前导 1 并且它消失了，其他 52 位按字面意思复制到结果 double 的有效位.但是，如果该位未设置，则其余位必须左移，直到设置为止。

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

1:并非总是如此，显然它不能对没有最高 1 的零进行。这些数字称为非正规数或次正规数，请参阅 wikipedia:denormal number .