Java - 通过转换为double来查找长的前导零

Question

在找到方法Long.numberOfLeadingZeros(long i)之前,我正在使用Math.getExponent(double d)将longs转换成双精度数.想法是找到long的双重表示,使用指数获得最高设置位,并从64减去它以获得前导零的数量.

这大部分都有效,但偶尔会被1关闭.以下for循环用于突出显示问题:

for (int i = 0; i < 64; i++) {
    double max = Long.MAX_VALUE >>> i;
    double min = Long.MIN_VALUE >>> i;
    double neg = -1L >>> i;
    System.out.format("Max: %-5d Min: %-5d -1: %-5d%n", Math.getExponent(dmax),
                                Math.getExponent(dmin), Math.getExponent(dneg));
}

占产出的重要部分:

...
Max: 55    Min: 55    -1: 56   
Max: 54    Min: 54    -1: 55   
Max: 52    Min: 53    -1: 54   
Max: 51    Min: 52    -1: 52   
Max: 50    Min: 51    -1: 51
...  

设置所有位的长整数在2 ^ 52之上偏离1.正如这篇文章所解释的那样,由于在52位尾数中存储了53个以上的有效位,因此会出现精度损失.但是,我很难理解为什么指数会受到影响.

虽然我不再使用这种方法,但我仍然很好奇:为什么以及在什么情况下这种在长时间内找到前导零的方法会失败？

Answer 1

a 的精度限制double强制二进制表示形式向上舍入到最接近的 的幂2，这会增加该值的浮点表示形式中的指数double。出现这种情况是因为 double 的尾数（包括隐含1位）为 53 位，而 along为 64 位。

\n\n

JLS 的第 5.1.2 节介绍了在这种扩大的原语转换中可能发生的情况：

\n\n

\n

从 int 到 float、从 long 到 float、或从 long 到 double 的加宽基元转换可能会导致精度损失 - 也就是说，结果可能会丢失该值的一些最低有效位。在这种情况下，生成的浮点值将是整数值的正确舍入版本，使用 IEEE 754 舍入到最近模式 (\xc2\xa74.2.4)。

\n

\n\n

（强调我的）

\n\n

在这里，我用来保留a 中的Double.doubleToLongBitsa 的位，并打印出原始s 的十六进制值。doublelongLong.toHexStringdouble

\n\n

System.out.format("Max(%s): %-5d Min(%s): %-5d -1(%s): %-5d%n",\n                Long.toHexString(Double.doubleToLongBits(dmax)), Math.getExponent(dmax),\n                Long.toHexString(Double.doubleToLongBits(dmax)), Math.getExponent(dmin),\n                Long.toHexString(Double.doubleToLongBits(dneg)), Math.getExponent(dneg));\n

\n\n

输出：

\n\n

Max(43e0000000000000): 63    Min(43e0000000000000): 63    -1(bff0000000000000): 0    \nMax(43d0000000000000): 62    Min(43d0000000000000): 62    -1(43e0000000000000): 63   \nMax(43c0000000000000): 61    Min(43c0000000000000): 61    -1(43d0000000000000): 62   \nMax(43b0000000000000): 60    Min(43b0000000000000): 60    -1(43c0000000000000): 61   \nMax(43a0000000000000): 59    Min(43a0000000000000): 59    -1(43b0000000000000): 60   \nMax(4390000000000000): 58    Min(4390000000000000): 58    -1(43a0000000000000): 59   \nMax(4380000000000000): 57    Min(4380000000000000): 57    -1(4390000000000000): 58   \nMax(4370000000000000): 56    Min(4370000000000000): 56    -1(4380000000000000): 57   \nMax(4360000000000000): 55    Min(4360000000000000): 55    -1(4370000000000000): 56   \nMax(4350000000000000): 54    Min(4350000000000000): 54    -1(4360000000000000): 55   \nMax(433fffffffffffff): 52    Min(433fffffffffffff): 53    -1(4350000000000000): 54   \nMax(432ffffffffffffe): 51    Min(432ffffffffffffe): 52    -1(433fffffffffffff): 52   \n

\n\n

long超过 53位的原始值1在转换为 时会向上舍入double，从而损失精度。指数字段由2位到12位组成，在上面打印的前 3 个十六进制数字中可见。

\n\n

当值移动到 531位以下时，double精度现在足以保持该值而无需舍入（不再需要向上舍入），并且尾数的位将变为可见的十六进制数字。435从到的指数域存在不连续性，这解释了为什么从到 的433结果存在不连续性。Math.getExponent5452

\n