How can I safely average two unsigned ints in C++?

Question

Using integer math alone, I'd like to "safely" average two unsigned ints in C++.

What I mean by "safely" is avoiding overflows (and anything else that can be thought of).

For instance, averaging 200 and 5000 is easy:

unsigned int a = 200;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2600 as intended

But in the case of 4294967295 and 5000 then:

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2499 instead of 2147486147

The best I've come up with is:

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a / 2) + (b / 2); // Equals: 2147486147 as expected

Are there better ways?

Answer 1

Use a 64-bit unsigned int as the placeholder for the sum, cast back to int after dividing by 2. Questionable whether this is 'better', but you certainly avoid the overflow issue with minimal effort.

Answer 2

unsigned int average = low + ((high - low) / 2);

EDIT

Here's a related article: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Answer 3

Your last approach seems promising. You can improve on that by manually considering the lowest bits of a and b:

unsigned int average = (a / 2) + (b / 2) + (a & b & 1);

This gives the correct results in case both a and b are odd.

Answer 4

What you have is fine, with the minor detail that it will claim that the average of 3 and 3 is 2. I'm guessing that you don't want that; fortunately, there's an easy fix:

unsigned int average = a/2 + b/2 + (a & b & 1);

This just bumps the average back up in the case that both divisions were truncated.

Answer 5

Your method is not correct if both numbers are odd eg 5 and 7, average is 6 but your method #3 returns 5.

Try this:

average = (a>>1) + (b>>1) + (a & b & 1)

with math operators only:

average = a/2 + b/2 + (a%2) * (b%2)

Answer 6

Not sure if the is better, but division by powers of 2 can be done with a >> k, so

unsigned int average = ( a >> 1 ) + ( b >> 1 );

Answer 7

If the code is for an embedded micro, and if speed is critical, assembly language may be helpful. On many microcontrollers, the result of the add would naturally go into the carry flag, and instructions exist to shift it back into a register. On an ARM, the average operation (source and dest. in registers) could be done in two instructions; any C-language equivalent would likely yield at least 5, and probably a fair bit more than that.

Incidentally, on machines with shorter word sizes, the differences can be even more substantial. On an 8-bit PIC-18 series, averaging two 32-bit numbers would take twelve instructions. Doing the shifts, add, and correction, would take 5 instructions for each shift, eight for the add, and eight for the correction, so 26 (not quite a 2.5x difference, but probably more significant in absolute terms).

Answer 8

If you don't mind a little x86 inline assembly, you can do it in three instructions:

unsigned average(unsigned x, unsigned y)
{
    asm("mov 8(%ebp), %eax");
    asm("add 12(%ebp), %eax");
    asm("rcr %eax");
}