Finding Average is no longer easy

Do you think you are good in Programming?
Then solve the following problem.

Write a program to find the average of two integers.

I too thought this is very easy before, till I found the problem. Lets look at the code for finding the average of two numbers.

The detailed specification.

A class Average with a method average() which takes 2 integers as parameters, and returns the average of the two numbers with the decimal part truncated.

Template for this program.

public class Average{
public static int average(int a, int b){
// your code here.
}
}

Sample input and output:

1. { 5, 10 } --> 7 // That is 7.5 truncate to 7
2. { 6, 10 } --> 8
3. { 5, 5 } --> 5
4. {-5, 10 } --> 2
5. {-5, -3 } --> -4

Looks Simple?

Simple Solution (But wrong):

Now, you would have come up with the solution

public class Average{
public static int average(int a, int b){
return (a+b)/2;
}
}
This would be the solution that most programmers (including me) will give.

But there is a big bug in this code.
Yes!

call the method as
Average.average(Integer.MAX_VALUE,1);
or
Average.average(2147483647,1);

Expected Result:
1073741824
Actual Result:
-1073741824

The two numbers are positive. Both the arguments are valid integers. Any mathematician can prove that the average of two integers will be within the range of the smallest number and the largest number.
So I should get only a positive return value.

What went wrong, in our program?

The great culprit is Integer overflow.

Integer.MAX_VALUE = 2147483647 = 0x7FFFFFFF
a = 0x7FFFFFFF
b = 0x00000001
----------------
a+b = 0x80000000 // Value is negative.
----------------
/2 = 0xC0000000 // Since Sign bit is reset to '1' after division

That is the integer overflows before we divide the numbers by 2. This creates the problem.

Solution:

public class Average{
public static int average(int a, int b){
return (a+b) >>> 1;
}
}

That is, in Java we have a bit-wise operator that right shifts along with the sign bit. This will solve the problem. But what if we have to find the average of 3 integers, then for 'n' integers? This is not easy to extend.

Another solution is,

public class Average{
public static int average(int a, int b){
int high = a>b?a:b;
int low = a<=b?a:b; return (low+(high-low)/2);
}
}

This is also not easy to extend, but atleast gives some hope to extend. But surely not easy.
I leave the assignment to find the average of 'n' integers correctly to the readers, to appreciate the difficulty of finding the average.

Binary Search:

If you think why we need an integer average, instead of a float, consider the example of finding the median in an array. To find the middle element, we will use the above specified function. Also, the well known Binary Search algorithm is another example that needs the above function.

In Java, the binary search algorithm is implemented using the initial version of the code.
The java.util.Arrays class implements the binary search algorithm. Have a look at the Java source code.

public static int binarySearch(int[] a, int key) {
int low = 0;
int high = a.length-1;

while (low <= high) {
int mid = (low + high) >> 1;
int midVal = a[mid];

if (midVal <>
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}

The line mid = (low + high)>>1 contains the bug. It is exactly equivalent to dividing by 2.

A bug is reported in Sun' Bug Database.

This piece of code was writen by Joshua Bloch, the author of Effective Java: Programming Language Guide, one of the must-read books for Java Developers.