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!..
Hello Dim,
ReplyDeletewhat about using the equality (x+y)/2 = x/2+y/2 ?
your old friend Kostas
Hello big Greek cryptographer! Years and zamans! :)
ReplyDeleteThis equality does not hold though (note this is integer division), it would compure the wrong answer when both x and y are odd (e.g. x=3,y=5, result=3 instead of 4).
Geia xara!
yeap, correct, in fact it does not hold when x and y are both same sign and odd. I tried a couple of times, but nothing was faster than your solution! Maybe in the case of floats or doubles I could have better chances!
ReplyDeleteK.
(Btw I wasn't accurate, "when both x and y are odd and of the same sign")
ReplyDeleteHa, collision!
ReplyDeleteFor floats/doubles, x/2 + y/2 should probably be fine. It's quite different though, if one uses floats/doubles, it implies he can tolerate slightly inexact math anyway.
hm... "it implies he can tolerate slightly inexact math anyway.", not always.. there are many reasons for choosing floats and doubles.. (i.e we need bigger numbers than the long max_value, but we do not need other libraries such as BigInteger, or we just need a portion of the decimal digits and not all of them. Btw I was thinking of adding some %2 operations on the initial "int" problem... I am sure this brainteaser will follow me in the toilet.... :D
ReplyDeleteBigger numbers are always fun with doubles:
ReplyDeleteLong.MAX_VALUE + 1.0 == (double)Long.MAX_VALUE
(Well, 64 bits can only fit 64 bits of information!)
Also, x % 2 == x & 1 (but I hope the compiler transforms this anyway).
ps: too much information :P
How to Play Baccarat | FBCasino
ReplyDeleteThis variation is available in many variants – from traditional Baccarat to Roulette. It is choegocasino an Irish febcasino favourite, which means 메리트 카지노 the player who wishes to take