You might be tempted to think that calculating the average of two integers is a trivial thing. If you think that it is as easy as this:

you are wrong. But don’t be depressed — you are in good company. Code like this is written every day — not just by average developers.

(Task#1: Hold on for a minute. Can you spot any problems with this code?)

I’m not talking about the fact that the result is not precise — it can’t be, due to the limitations of the integer type. If ‘a’ is 5 and ‘b’ is 6, the mathematically correct result is 5.5. With integer division, however, it is 5, which is perfectly OK for our purposes; otherwise, we would have used ‘float’ or ‘double’. No, that’s not what I’m looking for…

The trouble is that if a developer looks at the signature, (s)he will probably think “Well, this function takes two integers and returns their average value. I can pass ANY unsigned integer to this function.”, which is of course not true. Why? If the integers are large enough, their sum will overflow the unsigned int range and hence the result of the division will be wrong. There you have it!

(Task#2: Write tests that show when and how overflow happens.)

You could use a larger type internally:

but maybe ‘long long’ is not available on your platform, or you are already using ‘long long’ and there is no bigger type, or you simply don’t want to sacrifice efficiency, especially by using a floating point type. (Note that ‘long’ is not sufficient in our example as on 32-bit platforms ‘int’ and ‘long’ are usually of the same size). So how can you solve this problem without resorting to a larger (more expensive) type?

Years ago I found a solution (I don’t claim that I’m the first who invented this, and I won’t be the last to reinvent it, either) by reasoning like this:

In pure mathematical terms, with a mathematical division operator, (a + b) / 2 is identical to a / 2 + b / 2. By applying this principle — and “wasting” another division — one could avoid the dreaded overflow in the sum. Unfortunately, integer division doesn’t exactly work like mathematical division. For instance, if ‘a’ is 5 and ‘b’ is 7, (5 + 7) / 2 is 6, but 5 / 2 + 7 / 2 = 2 + 3, which is 5. So it is possible that the result is one less than what we expect. How can we compensate for that?

Here is the insight: For both divisions, the integer division operator leaves a remainder behind and if the sum of the remainders (of both divisions) is equal to two, we have to add 1 to our result. Think of it this way: in such cases, the sum of ‘a’ and ‘b’ contains a 2 more than the parts of the sum themselves:

Here is an implementation that applies this correction:

Unfortunately, this is not only ugly, it is not very efficient, either. Now we have two divisions, two modulo operations (which are as expensive as division operations), two additions, an if-statement and an increment operation. But as every bit-fiddler knows, there is a simpler modulo operation for divisors that are a power of two:

Equipped with this knowledge we get:

Which is identical to:

In C, results of boolean operations are either 0 or 1 (in C++, they are ‘false’ or ‘true’, but ‘false’ and ‘true’ are converted implicitly to 0 or 1 in arithmetic expressions), so we can shorten our average function:

Cool isn’t it? But it’s not unlikely that your compiler will apply these optimizations for you automatically, in case you write your code like in the first, ugly solution. But it certainly won’t add the correction that is missing from the first implementation — trust me on this one.

(Task#3: Write a small program that uses this implementation of average() and test it.)
(Task#4: If you change the types used by average() from ‘unsigned int’ to ‘int’, will the code also work, specifically for negative values of ‘a’ and ‘b’? Why? Write some tests to proof your theory.)
(Task#5: Implement and test an average4() function that calculates the average of four integers.)