Java

Question

在找到方法之前Long.numberOfLeadingZeros(long i), I was casting longs to doubles and using 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打印出原始[=的十六进制值12=]s.

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 不连续].

Answer 2

一个全为 1 的数字，当四舍五入到较少的位置时，会向上四舍五入，因此会变长一位。例如（假设 double 的尾数只有 5 位）

111111 becomes 1000000

四舍五入时。

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

Java - finding leading zeros in a long by conversion to double

precision

bit-manipulation