Java - 通过转换为 double 在 long 中查找前导零

Question

在找到方法之前Long.numberOfLeadingZeros(long i) ，我将多头投向 double 并使用 Math.getExponent(double d) .想法是找到 long 的 double 表示，使用指数获得最高设置位，然后从 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。 As this post explains,由于在 52 位尾数中存储了 53 个以上的有效位，会导致精度损失。但是，我很难理解为什么指数会受到影响。

虽然我不再使用这种方法，但我仍然很好奇:为什么以及在什么情况下，这种在 long 中查找前导零的方法会失败？

Answer 1

double 的精度限制强制二进制表示形式四舍五入到最接近的 2 次幂，这会增加浮点表示形式中的指数double 值。这是因为 double 的尾数(包括隐含的 1 位)是 53 位，而 long 有 64 位。

Section 5.1.2 of the JLS涵盖了在这种扩大的原始转换中可能发生的事情:

A widening primitive conversion from int to float, or from long to float, or from long to double, may result in loss of precision - that is, the result may lose some of the least significant bits of the value. In this case, the resulting floating-point value will be a correctly rounded version of the integer value, using IEEE 754 round-to-nearest mode (§4.2.4).

(强调我的)

在这里，我使用 Double.doubleToLongBits 将 double 的位保存在 long 中，并使用 Long.toHexString 打印出原始 double 的十六进制值。

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

输出:

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

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

当值移动到 53 1 位以下时，double 的精度现在足以保存该值而无需四舍五入(不再需要四舍五入)并且尾数的位变为可见的“f”十六进制数字。指数字段存在不连续性，从 435 到 433，解释了为什么 Math.getExponent 的结果不连续，从 54 到 52。