5 ms·

Same happens with integers. Try computing the mean of 3 and 4 using integer math. The only difference, really, is that floating point can lull you into believ

• panic 10y ago
  Yep! The addition here can overflow, too, just like in the integer case (though you'll get an infinite value instead of wraparound).
• dskloet 10y ago
  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.
  • ced 10y ago
    ... unless max is a huge positive integer, and min is a huge negative integer!
    • RUBwkVjwLsDKgPw 10y ago
      Just use signed ints. Signed integer underflow is undefined behavior so it can't happen /s
      • gcc_programmer 10y ago
        Lol'd . To the contrary, it _can_ happen, and when it does the behaviour is undefined for C/C++. However, rest assured - you are probably on a x86_64 machine programming in sth like Ruby or Java script, so your Apps should be alright :P
  • 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 ago
      Is there an explanation of how that actually works somewhere?
      • TimonKnigge 10y ago
        Yes 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 ago
          Great explanation, thanks.
      • pbsd 10y ago
        There'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
  • jameshart 10y ago
    That is the safe technique for common cases such as locating a pivot in an array - where min and max are guaranteed to be positive (or you're using unsigned ints in the first place). That approach doesn't solve the overflow problem in general for signed ints.
  • caf 10y ago
    Integer division doesn't round down, it rounds towards zero.
• deleted 10y ago
  [deleted]