Avoid subtraction based comparison between integers

Before I say anything I want to share with you a code snippet that is a simplified version of something I have recently wrote in my work. There is a small, yet painful bug in this code… can you see it?

public static class Point implements Comparable<Point> {
    private int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Point other) {
        if (this.x != other.x) {
            return this.x - other.x;
        } else {
            return this.y - other.y;
        }
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Point)) return false;
        Point other = (Point) obj;
        return (this.x == other.x && this.y == other.y);
    }

    @Override
    public int hashCode() {
        return 31 * x + y;
    }
}

This is a simple value class represanting a point. At first glance everything is good with it: the hash function is not sophisticated, but it is correct and legal. The equals() method is written ‘by the book’ so it is probably OK. The class implements Comparable interface and defines a lexicographic order of the points – the code of compareTo() is standard and fulfills the contract of the interface. All three methods are compatible with each other: hash codes of equal points are equal, comparisons are transitive, if A.compareTo(B) == 0 then A.equals(B)… Basically all is fine, so where is the bug? Is there any bug at all?
Unfortunatelly there is a bug in this code. What is worse you probably read about it many times (’Effective Java’ item 11, ‘Java Puzzlers’ puzzle 65, the list goes on an on…). The problem with this code is that substraction based comparators are BAD as they often exposes you to danger of an overflow. This is what happens in this case – see the following:

public static void main(String[] args) {
    Point pZero  = new Point(0, 0);
    Point pPlus  = new Point(2000000000, 0);
    Point pMinus = new Point(-2000000000, 0);

    System.out.println( pPlus.compareTo(pZero) > 0 );
    System.out.println( pZero.compareTo(pMinus) > 0 );
    System.out.println( pPlus.compareTo(pMinus) > 0 );
  }

We are comparing in this code three points. When you look at the declaration of those object you can already see the order of them: pPlus > pZero > pMinus. Just to be sure we check it by printing to console the result of compareTo() function. If you execute this code you’ll get that as expected ‘true’ for pPlus > pZero and ‘true’ for pZero > pMinus. The suprizing thing is the last comparison that evaluates to false. This is because of the integer overflow: in pPlus.compareTo(pMinus) the result value is 2000000000 – (-2000000000) == -294967296! Scary, right?

Immutable Objects / Wrapper Class Caching

Since Java 5, wrapper class caching was introduced.
The following is an examination of the cache created by an inner class, IntegerCache, located in the Integer cache. For example, the following code will create a cache:
Integer myNumber = 10; or Integer myNumber = Integer.valueOf(10);

256 Integer objects are created in the range of -128 to 127 which are all stored in an Integer array. This caching functionality can be seen by looking at the inner class, IntegerCache, which is found in Integer:

private static class IntegerCache 
{
private IntegerCache(){}

static final Integer cache[] = new Integer[-(-128) + 127 + 1];

static 
{
   for(int i = 0; i < cache.length; i++)
   cache[i] = new Integer(i - 128); 
   }
}

public static Integer valueOf(int i) 
{
   final int offset = 128;
   if (i >= -128 && i <= 127) // must cache 
   { 
      return IntegerCache.cache[i + offset];
   }
   return new Integer(i);
}

So when creating an object using Integer.valueOf or directly assigning a value to an Integer within the range of -128 to 127 the same object will be returned. Therefore, consider the following example:

Integer i = 100;
Integer p = 100;
if (i == p)  
System.out.println("i and p are the same.");
if (i != p)   
System.out.println("i and p are different.");    
if(i.equals(p))  
System.out.println("i and p contain the same value.");

The output is:
i and p are the same.
i and p contain the same value.

So this result is similar to the result as shown here for strings.

It is important to note that object i and p only equate to true because they are the same object, the comparison is not based on the value, it is based on object equality. If Integer i and p are outside the range of -128 or 127 the cache is not used, therefore new objects are created. When doing a comparison for value always use the “.equals” method. It is also important to note that instantiating an Integer does not create this caching. So consider the following example:

Integer i = new Integer (100);
Integer p = new Integer(100);
if(i==p) 
System.out.println(“i and p are the same object”);
if(i.equals(p)) 
System.out.println(“ i and p contain the same value”);

In this circumstance, the output is only: i and p contain the same value

The other wrapper classes (Byte, Short, Long, Character) also contain this caching mechanism OR constant pooling mechanism. The Byte, Short and Long all contain the same caching principle to the Integer object. The Character class caches from 0 to 127. The negative cache is not created for the Character wrapper as these values do not represent a corresponding character. There is no caching for the Float object.

BigDecimal also uses caching but uses a different mechanism. While the other objects contain a inner class to deal with caching this is not true for BigDecimal, the caching is pre-defined in a static array and only covers 11 numbers, 0 to 10:

 

// Cache of common small BigDecimal values.
private static final BigDecimal zeroThroughTen[] = {
new BigDecimal(BigInteger.ZERO,        0,  0),
new BigDecimal(BigInteger.ONE,        1,  0),
new BigDecimal(BigInteger.valueOf(2),    2,  0),
new BigDecimal(BigInteger.valueOf(3),    3,  0),
new BigDecimal(BigInteger.valueOf(4),    4,  0),
new BigDecimal(BigInteger.valueOf(5),    5,  0),
new BigDecimal(BigInteger.valueOf(6),    6,  0),
new BigDecimal(BigInteger.valueOf(7),    7,  0),
new BigDecimal(BigInteger.valueOf(8),    8,  0),
new BigDecimal(BigInteger.valueOf(9),    9,  0),
new BigDecimal(BigInteger.TEN,        10, 0),
};

As per Java Language Specification(JLS) the values discussed above are stored as immutable wrapper objects. This caching has been created because it is assumed these values / objects are used more frequently.

Java: count the number of one bits in an int

Integer.bitCount counts the number of one-bits in the two's complement binary representation of the specified int value. Example code:

public class CountOnes {
    public static void main(String[] args) {
 int[] i = { 1, 4, 7, 15 };
 for (int j = 0; j < i.length; j++) {
     System.out.printf("Number of 1's in %d: %d\n", i[j], Integer.bitCount(i[j]));
 }
    }
}

The shift operators- << , >> , >>>(3 operators) for int and long

The shift left operator in Java technology is "<<". There are two operators for doing the right shift - signed right shift (>>) and zero fill right shift (>>>). The left shift operator fills the right bits by zero. The effect of each left shift is multiplying the number by two. The example below illustrates this - int i = 13; // i is 00000000 00000000 00000000 0000 1101 
i = i << 2; // i is 00000000 00000000 00000000 0011 0100

 After this left shift, i becomes 52 which is same as multiplying i by 4 Zero fill shift right is represented by the symbol >>>. This operator fills the leftmost bits by zeros. So the result of applying the operator >>> is always positive. (In two's complement representation the leftmost bit is the sign bit. If sign bit is zero, the number is positive, negative otherwise.) The example below illustrates applying the operator >>> on a number.  
int b = 13; // 00000000 00000000 00000000 0000 1101 
b = b >>> 2; // b is now 00000000 00000000 00000000 0000 0011

So the result of doing a zero fill right shift by 2 on 13 is 3. The next example explains the effect of applying the operator >>> on a negative number.  
int b = -11; //11111111 11111111 11111111 1111 0101 
b = b >>> 2; // b now becomes 00111111 11111111 11111111 1111 1101
So the result of applying zero fill right shift operator with operand two on -11 is 1073741821. Signed right shift operator (>>) fills the left most bit by the sign bit. The result of applying the signed shift bit has the same sign as the left operand. For positive numbers the signed right shift operator and the zero fill right shift operator both give the same results. For negative numbers, their results are different. The example below illustrates the signed right shift.  

int b = -11; // 11111111 11111111 11111111 1111 0101 

b = b >> 2; // 11111111 11111111 11111111 1111 1101 (2's complement of -3) // Here the sign bit 1 gets filled in the two most significant bits. 
The new value of b becomes -3.


1. How to generate a random number between 1 to x, x being a whole number greater than 1

Ans: double result = x * Math.random();

Mutable Integers in java

Because only objects (not primitives) can be stored in Collections data structures, the integer count must be an object, not just an int. The natural choice would be the Integer wrapper type, but it is immutable, which means that once an Integer object is created, its value can never be changed. But here we need to update the value, so here's a class that stores an int that can be changed.

//////////////////////////////////////////////////////////////// value class Int
/** Utility class to keep int as Object but allow changes (unlike Integer).
 * Java collections hold only Objects, not primitives, but need to update value.
 * The intention is that the public field should be used directly.
 * For a simple value class this is appropriate.
 */
class Int {
    //=================================================================== fields
    public int value;  // Just a simple PUBLIC int.  
    
    //============================================================== constructor
    /** Constructor 
        @param value Initial value. */
    public Int(int value) { 
        this.value = value;  
    }
}

Input functions in java (UDFs)

Inputing strings
public int inputInt() throws IOException
{
    int k=0;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String str;
    str = br.readLine();
    k = Integer.parseInt(str);
    return k;
           
}
For inputing integers
public int inputInt() throws IOException
{
    int k=0;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String str;
    str = br.readLine();
    k = Integer.parseInt(str);
    return k;
           
}