Java - finding leading zeros for a long time by converting to double

Question

Prior to searching for the Long.numberOfLeadingZeros (long i) method, I increased the doubling time and used Math.getExponent (double d) . The idea was to find a double representation of long, use the exponent to get the highest bit of the set, and subtract it from 64 to get the number of leading zeros.

This basically worked, but was sometimes turned 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 a significant portion of the 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 lengths with all bits set are disabled by 1 above 2 ^ 52. As explained in this post , accuracy loss occurs due to the storage of 53+ significant bits in a 52-bit mantissa. However, I am struggling to understand why the exponent is affected.

While I no longer use this method, I'm still wondering: why and under what circumstances is this method of finding leading zeros in a long-term failure?

Answer 1

The precision limit on double causes the binary representation to round to the nearest power of 2 , which increases the exponent in the floating point representation of the double value. This is because the double mantissa, including implied bit 1 , is 53 bits, but long has 64 bits.

JLS Section 5.1.2 describes what can happen in this expanding primitive transformation:

An expanding primitive conversion from int to float or from long to float or from long to double can lead to a 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 the round-nearest mode of IEEE 754 (§4.2.4).

(my emphasis)

Here I use Double.doubleToLongBits to store the double bits in long and Long.toHexString to print the hexadecimal values ​​of the original double 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)); 

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 

Original long values ​​with more than 53 1 bits are rounded when converted to double , losing precision. The exponent field consists of bits 2 through 12 , visible in the first three hexadecimal digits printed above.

When a value shifts below 53 1 bit, the precision of double now sufficient to hold the value without rounding (rounding is no longer required), and the mantissa bits become visible as "f" hexadecimal digits. There is a gap in the exponent field going from 435 to 433 , explaining why there is a gap as a result of Math.getExponent , from 54 to 52 .

Answer 2

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

 111111 becomes 1000000 

when rounding.