Take the average of two signed numbers in C

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);
}

If (a^b)<=0 you can just use (a+b)/2 without fear of overflow.

Otherwise, try (a-(a|b)+b)/2+(a|b)/2. -(a|b) is at least as large in magnitude as both a and b and has the opposite sign, so this avoids the overflow.

I did this quickly off the top of my head so there might be some stupid errors. Note that there are no machine-specific hacks here. All behavior is completely determined by the C standard and the fact that it requires twos-complement, ones-complement, or sign-magnitude representation of signed values and specifies that the bitwise operators work on the bit-by-bit representation. Nope, the relative magnitude of a|b depends on the representation...

Edit: You could also use a+(b-a)/2 when they have the same sign. Note that this will give a bias towards a. You can reverse it and get a bias towards b. My solution above, on the other hand, gives bias towards zero if I'm not mistaken.

Another try: One standard approach is (a&b)+(a^b)/2. In twos complement it works regardless of the signs, but I believe it also works in ones complement or sign-magnitude if a and b have the same sign. Care to check it?