It's not the same. With integer division you know the division rounds down, so using <= always splits between the two points.
That said, it's always safer to compute the mean of two integers as
min + (max - min) / 2
to avoid integer overflow.
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 int mid = (low + high) >>> 1;
int mid =(low + high) / 2;
More info: https://research.googleblog.com/2006/06/extra-extra-read-all...
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 :)
[1] http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item23