Homework: Integer Average

Consider the following contract specification for the static method average . Please note that, both in the specification and in the Java programming language, the integer-division (' / ') operator's result is obtained by truncating toward zero. Hence, (-3 / 2) = -1 and (9 / 2) = 4 . It is like "rounding", except that the quotient given as the result is not necessarily the closest integer to the correct rational quotient: it is the first-encountered integer closer to zero than the correct rational quotient.

    /**
     * Returns the integer average of two given {@code int}s.
     * 
     * @param j
     *            the first of two integers to average
     * @param k
     *            the second of two integers to average
     * @return the integer average of j and k
     * @ensures average = (j+k)/2
     */
    public static int average(int j, int k) {...}

Answer the following questions.

1. Provide an argument justifying the following claim: The average (as defined here) of two Java ints i and j is representable as an int, regardless of the lower and upper bounds on the value of an int.
2. Provide an implementation of the average method with int as the only type you use (except, perhaps, for boolean). Note: return (j+k)/2; does not implement the contract specification. Some of the test cases shown below will reveal defects in this obvious implementation. Your challenge is to figure out a way or ways to work around the fact that, if a sum is non-representable as an int (has overflowed), then Java arranges that the value provided at run-time is wrong. In other words, each arithmetic operation has a precondition that requires that the result is representable in its type. Your challenge includes making sure that this precondition is always satisfied. As you find ways to do so, you'll also need to work out difficulties involved with the truncating going in the wrong direction, as compared with the truncation direction established in the contract specification. (By the way, because it is mathematics, the expressions in contract specifications always mean the right answer; in contract specifications, there is no overflow.) Each of the following is a valid test case for the average method.

   Test	Input values		Expected result
   	j	k	return
   1	Integer.MAX_VALUE	Integer.MAX_VALUE - 1	Integer.MAX_VALUE - 1
   2	Integer.MIN_VALUE	Integer.MIN_VALUE + 1	Integer.MIN_VALUE + 1
   3	Integer.MIN_VALUE	Integer.MIN_VALUE	Integer.MIN_VALUE
   4	Integer.MAX_VALUE	Integer.MAX_VALUE	Integer.MAX_VALUE
   5	5	8	6
   6	-5	-8	-6
   7	11	-4	3
   8	-3	2	0
   9	3	5	4
   10	-3	-5	-4
   11	-3	4	0