How about...
(x + y) / 2
Well, that doesn't work when (x + y) can overflow, and in fact this buggy implementation was lurking in the binary-search and mergesort implementations of JDK till recent years. (Obligatory Josh Bloch link: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html)
It's an interesting puzzle for you to meditate and try out yourself - it looks simple, but it's not. I have yet to find a simple solution that works without assumptions on x, y - just any ints.
Blochs first solution is this:
x + (y - x) / 2
I.e. starting with x and adding half the distance to y. Only that this assumes that x,y > 0, otherwise y-x can itself overflow!
The second solution:
(x + y) >>> 1
Pretty nifty. If (x + y) does overflow, the high bit of the number (which determines the sign) will become one, i.e. negative, but >>> 1 will do the division and put a zero there. But what if (x + y) underflows (x, y are big negative numbers)? Oops.
So neither solution works for all cases.
Still working out a solution. In my case, I only need that average(x, y) != x && average(x, y) != y, when x and y are not consecutive ints. Any helping hand appreciated :)
My current solution:
static int avg(int x, int y) {
return diffSign(x, y) ? (x + y) / 2 : x + (y - x) / 2;
}
static boolean diffSign(int x, int y) {
return (x ^ y) < 0;
}
diffSign returns true iff x and y do not have the same sign. In that case only, (x + y) is safe. Otherwise, (y - x) is safe, so I go for that option. This solution works for corner cases (like Integer.MIN_VALUE) too. Well, I don't think I can get it any simpler (assuming it's really correct). Can you?
-edit-
It turns out there is a much more elegant solution, which is provably correct, found here.
static int avg(int x, int y) {
return (x & y) + (x ^ y) / 2;
}
Wow!..
-edit-
It turns out there is a much more elegant solution, which is provably correct, found here.
static int avg(int x, int y) {
return (x & y) + (x ^ y) / 2;
}
Wow!..
