3 ms·
I like this one better: (min&max) + ((min^max) >> 1) #include <iostream> using namespace std; int avg(int a, int b) { return (a&b) + ((a^b)>>1); }
by TimonKnigge 10y ago
I like this one better: (min&max) + ((min^max) >> 1)
#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;
}
Gives:
2000000005
0
-2000000005
- Retr0spectrum 10y agoIs there an explanation of how that actually works somewhere?
- TimonKnigge 10y agoYes there is! Right here: It's actually really simple. We'll write a and b in binary notation, for example: a = 1001101 b = 0100111 Now what happens when you add two numbers in binary? We essentially add the numbers in each column together, and if it overflows, we carry to the next column (this is how you carry out addition in general). 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 :)
- Retr0spectrum 10y agoGreat explanation, thanks.
- pbsd 10y agoThere's this well-known identity [1] a + b = (a ^ b) + ((a & b) << 1). This is essentially how a parallel ripple carry adder works. So (a + b) / 2 = (a + b) >> 1 = ((a ^ b) >> 1) + (a & b). [1] http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item23 http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item23
- Avshalom 10y agoIt's pretty obvious visually, you take the exclusive disjunct (a^b -> yellow) divide by two (>>1 -> bright yellow) and then add the intersection (a&b -> green) you use the full intersection because in the basic method (a+b / 2) they would each add their own half of the intersection. https://imgur.com/PUT4G9Z https://imgur.com/PUT4G9Z
- luc4sdreyer 10y agoReminds me of the way Java's binary search computes the average: int mid = (low + high) >>> 1; This was a fix because the original code had a bug: int mid =(low + high) / 2; Which was part of the Java code base for many years. Joshua Bloch based the code on Programming Pearls, which also contained the bug. More info: https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://research.googleblog.com/2006/06/extra-extra-read-all...