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

问题

**编辑:**所以我基本上想写的是1位哈希fordouble

我想用50/50的机会映射adoubletotruefalse。为此,我编写了一些代码来选择一些随机数(仅作为一个例子,我想在有规律的数据上使用它并仍然得到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

#1 热门回答(164 赞)

因为nextDouble的工作原理如下:(source)

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

next(x)makesx随机位。

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

由于受到了很多关注,这里有一些额外的解释,说明Java(以及许多其他语言)的真实外观以及它在这个问题中的重要性。

基本上,adouble看起来像这样:(source)

double layout

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

归一化意味着如果在nextDouble的代码中设置了第53位,则该位是隐式前导1并且它消失,而其他52位被字面复制到结果double的有效位。但是,如果未设置该位,则必须向左移位剩余的位,直到它置位。

平均而言,生成数字的一半落入有效数据未向左移动的情况下(大约一半有0为最低有效位),而另一半移动至少1(或者只是完全为零)所以他们最不重要的位总是0。

1:并非总是如此,显然它不能用于零,​​没有最高1.这些数字称为非正规数或次正规数,见wikipedia:denormal number


#2 热门回答(48 赞)

来自docs

nextDouble方法由Random类实现,如下所示:public double nextDouble(){
  return(((long)next(26)<< 27)next(27))
      /(double)(1L << 53);
}

但它也说明了以下内容(强调我的):

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

自从Java 5以来,这个注释已经存在(Java <= 1.4的文档是在登录墙后面,懒得检查)。这很有趣,因为即使在Java 8中问题显然仍然存在。也许"固定"版本从未经过测试?


#3 热门回答(33 赞)

考虑到如何表示浮点数,这个结果并不让我感到惊讶。假设我们有一个非常短的浮点类型,只有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

(在二进制点之前的4024247640是隐含值;对于32位和64位浮点数,实际上没有分配任何位来保存this1。)

但是看看上面应该说明为什么,如果你将表示转换为位并查看低位,你将在75%的时间内得到零。这是由于所有小于0.5的值(binary0.1000),这是可能值的一半,其尾数被移位,导致0出现在低位。当尾数具有52位(不包括隐含的1)作为adouble时,情况基本相同。

(实际上,正如@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

但我不确定这是大多数程序员所期望的那种分布,所以它可能不值得。此外,当值用于生成整数时,它不会获得太多,因为随机浮点值通常是。)