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

Question

Prior to finding the method Long.numberOfLeadingZeros(long i), I was casting longs to doubles and using Math.getExponent(double d). The idea was to find the double representation of the long, use the exponent to get the highest set bit, and subtract it from 64 to get the number of leading zeros.

This mostly worked, but was occasionally off by 1. The following for-loop was used to highlight the problem:

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));
}

with the significant portion of output:

...
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
...

The longs with all bits set are off by 1 above 2^52. As this post explains, a loss of precision occurs due to the storage of 53+ significant bits in the 52-bit mantissa. However, I am struggling to understand why the exponent is affected.

While I am no longer using this method, I am still curious: why and under what circumstances does this method of finding the leading zeros in a long fail?

score 3 · Accepted Answer · answered Nov 16 '15 at 19:27

The limit of precision on a double forces the binary representation to round up to the nearest power of 2, which increments the exponent in the floating-point representation of the double value. This occurs because a double's mantissa, including the implied 1 bit, is 53 bits, but a long has 64 bits.

Section 5.1.2 of the JLS covers what may happen in this widening primitive conversion:

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).

(emphasis mine)

Here, I use Double.doubleToLongBits to preserve the bits of a double in a long, and Long.toHexString to print out the hex values of the original doubles.

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));

Output:

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

The original long values with more than 53 1 bits are rounded up when converted to a double, losing precision. The exponent field consists of bits 2 through 12, visible in the 1st 3 hex digits printed out above.

When the value is shifted below 53 1 bits, double's precision is now sufficient to hold the value without rounding (the round up is no longer necessary) and the mantissa's bits become visible as 'f' hex digits. There is a discontinuity in the exponent field, going from 435 to 433, explaining why there is a discontinuity in the result of Math.getExponent, from 54 to 52.

This makes perfect sense. After reading your post, I forced values greater than 2^53 - 1 to drop their 11 least significant bits by: 'value &= 0xFFFFFFFFFFFFF700L;' prior to conversion to a double, making rounding unnecessary. I also forgot the mantissa has the extra implied bit. Thanks for the detailed answer! — Dave B., Nov 16 '15 at 20:40

score 1 · Answer 2 · answered Nov 16 '15 at 19:28

1

A number with all ones, when rounded to fewer places will be rounded up and therefore become one bit longer. For example (assume a double has only 5 bits in the mantissa)

111111 becomes 1000000

when rounded.

answered Nov 16 '15 at 19:28

Henry

42,982
7
68
84

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

2 Answers2