Take the average of two signed numbers in C

Question

Let us say we have x and y and both are signed integers in C, how do we find the most accurate mean value between the two?

I would prefer a solution that does not take advantage of any machine/compiler/toolchain specific workings.

The best I have come up with is:(a / 2) + (b / 2) + !!(a % 2) * !!(b %2) Is there a solution that is more accurate? Faster? Simpler?

What if we know if one is larger than the other a priori?

Thanks.

D

---

Editor's Note: Please note that the OP expects answers that are not subject to integer overflow when input values are close to the maximum absolute bounds of the C int type. This was not stated in the original question, but is important when giving an answer.

Answer 1

For unsigned integers the average is the floor of (x+y)/2. But the same fails for signed integers. This formula fails for integers whose sum is an odd -ve number as their floor is one less than their average.

You can read up more at Hacker's Delight in section 2.5

The code to calculate average of 2 signed integers without overflow is

int t = (a & b) + ((a ^ b) >> 1)
unsigned t_u = (unsigned)t
int avg = t + ( (t_u >> 31 ) & (a ^ b) )

I have checked it's correctness using Z3 SMT solver

Answer 2

After accept answer (4 yr)

I would expect the function int average_int(int a, int b) to:
1. Work over the entire range of [INT_MIN..INT_MAX] for all combinations of a and b.
2. Have the same result as (a+b)/2, as if using wider math.

When int2x exists, @Santiago Alessandri approach works well.

int avgSS(int a, int b) {
  return (int) ( ((int2x) a + b) / 2);
}

Otherwise a variation on @AProgrammer:
Note: wider math is not needed.

int avgC(int a, int b) {
  if ((a < 0) == (b < 0)) {  // a,b same sign
    return a/2 + b/2 + (a%2 + b%2)/2;
  }
  return (a+b)/2;
}

A solution with more tests, but without %

All below solutions "worked" to within 1 of (a+b)/2 when overflow did not occur, but I was hoping to find one that matched (a+b)/2 for all int.

---

@Santiago Alessandri Solution works as long as the range of int is narrower than the range of long long - which is usually the case.

((long long)a + (long long)b) / 2

---

@AProgrammer, the accepted answer, fails about 1/4 of the time to match (a+b)/2. Example inputs like a == 1, b == -2

a/2 + b/2 + (a%2 + b%2)/2

---

@Guy Sirton, Solution fails about 1/8 of the time to match (a+b)/2. Example inputs like a == 1, b == 0

int sgeq = ((a<0)==(b<0));
int avg = ((!sgeq)*(a+b)+sgeq*(b-a))/2 + sgeq*a;

---

@R.., Solution fails about 1/4 of the time to match (a+b)/2. Example inputs like a == 1, b == 1

return (a-(a|b)+b)/2+(a|b)/2;

---

@MatthewD, now deleted solution fails about 5/6 of the time to match (a+b)/2. Example inputs like a == 1, b == -2

unsigned diff;
signed mean;
if (a > b) {
    diff = a - b;
    mean = b + (diff >> 1);
} else {
    diff = b - a;
    mean = a + (diff >> 1);
}