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

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 2

If you know ahead of time which one is higher, a very efficient way is possible. Otherwise you're better off using one of the other strategies, instead of conditionally swapping to use this.

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

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