The only difference, really, is that floating point can lull you into believing they have unlimited precision. With integer math, the problem would have been more obvious in the first place.
That said, it's always safer to compute the mean of two integers as
min + (max - min) / 2
to avoid integer overflow.
#include <iostream>
using namespace std;
int avg(int a, int b) {
return (a&b) + ((a^b)>>1);
}
int main() {
cout << avg(int(2e9), int(2e9 + 10)) << endl;
cout << avg(int(2e9), int(-2e9)) << endl;
cout << avg(int(-2e9), int(-2e9 - 10)) << endl;
return 0;
}
2000000005
0
-2000000005[1] http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item23
It's actually really simple. We'll write a and b in binary notation, for example:
a = 1001101
b = 0100111
So what are the columns where we need to carry, the ones that overflow? These are given by (a&b) - the columns where both a and b contain a one. To actually carry we just move everything one position to the left: ((a&b)<<1). And what are the columns where we don't need to carry, the ones that don't overflow? These are the ones where we have exactly one zero, either in a or in b, so: a^b.
In other words, a + b = ((a&b)<<1) + (a^b). To compute the average, we divide by two, or in other words, we bitshift to the right by one place: (a + b)/2 = (a&b) + ((a^b)>>1)
If anything is unclear, feel free to ask :)
int mid = (low + high) >>> 1;
int mid =(low + high) / 2;
More info: https://research.googleblog.com/2006/06/extra-extra-read-all...