Calculating the average of two integers without overflow

Photo by Hope House Press — Leather Diary Studio on Unsplash

Let’s calculate the average of two integers and return the average as an INT. The usual approach is integer division of two integers and taking floor value of the floating-point result.

avg = floor((a + b) / 2)

But if any is these two values areINT_MAX for C\C++ or std::i32::MAX in Rust; it will cause an overflow.

Rust compiler will show something as follows:

thread ‘main’ panicked at ‘attempt to add with overflow’,

So the following piece of code will give us the average without any overflow.

fn average_without_overflow(a: i32, b: i32) -> i32 {
    return (a & b) + ((a ^ b) >> 1);
}

How does this trick work?

The sum of an integer can be written as follows:

sum = carries + sum without carries

To calculate the above we can do the following:

a + b = ((a & b) << 1) + (a ^ b)                    [Eq.1]

Now dividing by 2 is the same as 1 bit right shift.

Therefore,

(a + b) / 2 = (a + b) >> 1                          [Eq.2]

Combining [Eq.1] and [Eq.2]:

(a + b) / 2 = (a + b) >> 1 
            = ((( a & b ) << 1) + (a ^ b)) >> 1
            = (a & b) + ((a ^ b) >> 1)              [Eq.3]

Where >> is distributive.

Example:

Let’s imagine we have a calculator that has only three registers to store data. Therefore, the max decimal digit the calculator will be able to handle in 9 or 111 in binary.

Let’s take two INTa = 5 and b = 6 . Here b' denotes binary representation.

a = b'101
b = b'110

Their integer sum will be

a + b = 11 (decimal)
      = b'1011 (We can see it overflows)

So we have no space to keep the most significant bit here. (Asume our numbers are big-endian).

Let’s apply the [Eq.3]

a ^ b = b'101 ^ b'110
      = b'011
a & b = b'101 & b'110
      = b'100
(a ^ b) >> 1 = b'011 >> 1
             = b'001 (so dividing 1 by 2 is making the MSB 0)

Finally,

(a & b) + (a ^ b) >> 1 = b'100 + b'001
                       = b'101
                       = 5

Hope this example helps to get a clear picture.

The Rust code can be found here. https://gist.github.com/eNipu/6e8c3917865a4eb1e8cb34184d954d28

It will also work for C/C++. But not python since Python ints are arbitrary precision. We can verify the correctness of this trick using Python.