Concern public number: IT elder brother, read a dry goods article every day, a year later you will find a different self.

Cause 1.

The reason that draws my attention to this point is a problem: The Max-points-on-a-line on Niu.com

The title describes it this way:

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Basically, give me the X and Y coordinates of some points, find the line that has the most points, and output the number of points on that line.

So I typed the following code:

import java.util.HashMap; import java.util.Map; //class Point { // int x; // int y; // Point(int a, int b) { x = a; y = b; } //} public class Solution { public int maxPoints(Point[] points) { if (points.length <= 2) { return points.length; } int max = 2; for (int i = 0; i < points.length - 1; i++) { Map<Float, Integer> map = new HashMap<>(16); // Record vertical count; The maximum number of Points currently in a line with Points[I]; And Points[I] int ver = 0, cur, dup = 0; for (int j = i + 1; j < points.length; j++) { if (points[j].x == points[i].x) { if (points[j].y ! = points[i].y) { ver++; } else { dup++; } } else { float d = (float)((points[j].y - points[i].y) / (double) (points[j].x - points[i].x)); map.put(d, map.get(d) == null ? 1 : map.get(d) + 1); } } cur = ver; for (int v : map.values()) { cur = Math.max(v, cur); } max = Math.max(max, cur + dup + 1); } return max; }}Copy the code

This code in my naive view is no problem, but there is no way, after a long time to check the error, I wrote the following code to run in the above code

Public static void main (String [] args) {int [] [] vals = {{2, 3}, {3}, {5, 3}}; Point[] points = new Point[3]; for (int i=0; i<vals.length; i++){ points[i] = new Point(vals[i][0], vals[i][1]); } Solution solution = new Solution(); System.out.println(solution.maxPoints(points)); }Copy the code

It outputs 2

In other words, it thinks that 3 minus 3 over 3 minus 2 is different than 3 minus 3 over -5 minus 2, right? What the hell…

After debugging, the preceding results are 0.0 and -0.0 respectively

Isn’t 0.0 equal to -0.0?

At this point I thought, oh my God, but I wrote the verification code:

System. Out. Println (= = 0.0 0.0);Copy the code

The result is True, no problem, I’m messed up…

There must be something wrong with the Java underlying code! I yes…

Another debug, I found this statement:

map.put(d, map.get(d) == null ? 1 : map.get(d) + 1);
Copy the code

I have a problem with map.get(). Its source code looks like this:

public V get(Object key) {
     Node<K, V> e;
     return (e = getNode(hash(key), key)) == null ? null : e.valu;
}
Copy the code

Hash () = hash(); hash() = hash();

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the code

Again, we’re comparing hashCode for h and key, so let’s look at the hashCode() function

public native int hashCode();
Copy the code

This is a local method, can not see the source code, well, then I use it to see, test it is not good, I wrote the following test code:

Public static void main(String[] args) {system.out.println (0.0 == -0.0); public static void main(String[] args) {system.out.println (0.0 == -0.0); System.out.println(new Float(0.0).hashCode() == new Float(-0.0).hashCode()); }Copy the code

‍

The result is True and False!!

The source has finally been found. 0.0 and -0.0 hashCode values are different!

After some revision, I passed the problem (there are some accuracy issues and you should have used BigDecimal, but Nikkn is less demanding. And then I thought that the only way to avoid the accuracy problem is to write the equation of the line Ax+By+C=0.)

Next, let’s look at what happens with the hashCode() function of real numbers:

2. Real hashCode ()

  • The hashCode method must consistently return the same integer if the same object is called multiple times during program execution, as long as the information used by the equals method’s comparison operation has not been modified.

  • If two objects are equal according to equals, then the hashCode method calling both objects must return the same integer result.

  • If two objects are not equal according to equals, the hashCode method does not necessarily return different integers. — Effective Java

So let’s see if 0.0 and -0.0 call equals equals:

System. The out. Println (new Float (0.0.) the equals (0.0 f)); System. The out. Println (new Float (0.0.) the equals (0.0) (Float) -);Copy the code

The output is True and False

Well, they don’t call equals() equally, which seems to satisfy the logic in the book

Float = equals

public boolean equals(Object obj) {
   return (obj instanceof Float) 
          && (floatToIntBits(((Float) obj).value) == floatToIntBits(value));
}
Copy the code

Something strange happened while converting Float to Bits, so I found the source of everything:

/** * Returns a representation of the specified floating-point value * according to the IEEE 754 floating-point "single format" bit * layout. * * <p>Bit 31 (the bit that is selected by the mask * {@code 0x80000000}) represents the sign of the floating-point * number. * Bits 30-23 (the bits that are selected by the mask * {@code 0x7f800000}) represent the exponent. * Bits 22-0 (the bits that are selected by the mask * {@code 0x007fffff}) represent the significand (sometimes  called * the mantissa) of the floating-point number. * * <p>If the argument is positive infinity, the result is * {@code 0x7f800000}. * * <p>If the argument is negative infinity, the result is * {@code 0xff800000}. * * <p>If the argument is NaN, the result is {@code 0x7fc00000}. * * <p>In all cases, the result is an integer that, when given to the * {@link #intBitsToFloat(int)} method, will produce a floating-point * value the same as the argument to {@code floatToIntBits} * (except all NaN values are collapsed to a single * "canonical" NaN value). * * @param value a floating-point number. * @return the bits that represent the floating-point number. */ public static int floatToIntBits(float value) { int result = floatToRawIntBits(value); // Check for NaN based on values of bit fields, maximum // exponent and nonzero significand. if (((result & FloatConsts.EXP_BIT_MASK) == FloatConsts.EXP_BIT_MASK) && (result & FloatConsts.SIGNIF_BIT_MASK) ! = 0) result = 0x7fc00000; return result; }Copy the code

This document is quite long, I also checked other materials, read for a long time and finally understand

That is, the semantics of Java floating point numbers generally follow the IEEE 754 binary floating point arithmetic standard. The IEEE 754 standard provides definitions for floating point infinity, negative infinity, negative zero, and NaN (non-numeric). In Java, special floating-point numbers are often confusing

“-0.0” is produced when a floating-point operation produces a negative floating-point number that is very close to zero and cannot be represented properly

We can print a wave of 0.0 and -0.0:

System. The out. Println (Float. FloatToIntBits (0.0) (Float). System. The out. Println (Float. FloatToIntBits (0.0) (Float) -); System. The out. Println (Float. FloatToRawIntBits (0.0 f)); System. The out. Println (Float. FloatToRawIntBits (0.0) (Float) -);Copy the code

Results:

0 0-2147483648-2147483648Copy the code

In other words, store -0.0 with 0x80000000

This is also the familiar integer.min_value

3. Summary

The representation of floating-point numbers in Java is complicated, especially when it involves -0.0, NaN, plus or minus infinity, and is not suitable as a Map key because it may not be what we expect

Concern public number: IT elder brother, read a dry goods article every day, a year later you will find a different self.