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

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

我想映射一个 double到 true或 false与一个50/50的机会。为此，我编写了一些代码，选择一些随机数 (作为一个例子，我想把它用在有规律性的数据上，仍然得到一个50/50的结果)，检查它们的最后一位，如果是1，则增加 y，如果是0，则增加 n。

然而，这段代码不断导致25% 的 y和75% 的 n。为什么不是五五分成呢？为什么是这样一个奇怪的，但直接的(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
9392 次浏览
小开
最佳答案

因为 nextDouble 的工作原理是这样的: (来源)

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

next(x)使 x成为随机位。

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

由于这个问题受到了广泛的关注，这里有一些关于 Java (以及其他许多语言)中的 double到底是什么样子的额外解释，以及为什么它在这个问题中很重要。

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

double layout

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

规范化意味着，如果在 nextDouble的代码中设置了第53位，那么这个位就是隐式的前导1，它消失了，其他52位被复制到结果 double的有效位。但是，如果该位没有设置，那么其余的位必须向左移动，直到设置为止。

平均而言，生成的数字中有一半的有效位是 没有向左偏移的(大约一半的有效位是0) ，而另一半的有效位至少偏移了1(或者完全是0) ，所以它们的最低有效位总是0。

1: 不总是，显然不能对0做，它没有最高值1。这些数称为非正态数或次正态数，参见 维基百科: 异常数。

小开

来自 医生:

方法 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的三倍！这种不一致性在实践中可能无关紧要，但我们追求完美。]

这个注释至少从 Java5开始就存在了(Java < = 1.4的文档位于登录墙之后，懒得检查)。这很有趣，因为即使在 Java8中，这个问题显然仍然存在。也许“固定”版本从未被测试过？

小开

考虑到浮点数是如何表示的，这个结果并不让我感到惊讶。假设我们有一个非常短的浮点类型，精度只有4位。如果我们生成一个0到1之间的均匀分布的随机数，就会有16个可能的值:

0.0000
0.0001
0.0010
0.0011
0.0100
...
0.1110
0.1111

如果他们在机器里是这个样子的话，你可以测试一下低阶比特，得到一个50/50的分布。但是，IEEE 浮点数表示为尾数的2次方; 浮点数中的一个字段表示2次方(加上一个固定偏移量)。选择2的幂，因此“尾数”部分始终是一个 > = 1.0和 < 2.0的数字。这意味着，实际上，除了 0.0000以外的数字将如下所示:

0.0001 = 2^(-4) x 1.000
0.0010 = 2^(-3) x 1.000
0.0011 = 2^(-3) x 1.100
0.0100 = 2^(-2) x 1.000
...
0.0111 = 2^(-2) x 1.110
0.1000 = 2^(-1) x 1.000
0.1001 = 2^(-1) x 1.001
...
0.1110 = 2^(-1) x 1.110
0.1111 = 2^(-1) x 1.111

(二进制点之前的 1是一个隐含值; 对于32位和64位浮点数，实际上没有分配任何位来保存这个 1。)

但是看看上面的例子应该可以解释为什么，如果你把表示转换成位，再看看低位，75% 的情况下你会得到零。这是由于所有值小于0.5(二进制 0.1000) ，这是一半的可能值，有他们的尾数移动，导致0出现在低位。当尾数和 double一样有52位(不包括隐含的1)时，情况基本上是相同的。

(实际上，正如@sneftel 在评论中所建议的，我们 可以在分布中包含超过16个可能的值，通过生成:

0.0001000 with probability 1/128
0.0001001 with probability 1/128
...
0.0001111 with probability 1/128
0.001000  with probability 1/64
0.001001  with probability 1/64
...
0.01111   with probability 1/32
0.1000    with probability 1/16
0.1001    with probability 1/16
...
0.1110    with probability 1/16
0.1111    with probability 1/16

但是我不确定它是大多数程序员所期望的那种发行版，所以它可能不值得。另外，当使用这些值来生成整数时(随机浮点值通常是这样的) ，它不会给您带来太多好处。)


提交答案