Average of two unsigned integers
Well, this should be an easy task, shouldn't it be?
unsigned avg = (a + b) / 2;
But this approach can fail due to integer overflow if the sum exceeds 232 - 1 (for 32 bit wide unsigned integers) especially in unsafe languages where such errors are left undetected.
There are various ways to rectify this, if we know or if we check which of the two numbers is larger, then we can
unsigned avg = (high - low) / 2 + low;
In C++ 20, we can use std::lerp from the <cmath> header to implement the above in a slightly more abstract way.
unsigned avg = std::lerp(low, high, 0.5f);
Algorithms which do not require knowing which one of the two numbers is larger also exist. One of them is presented in this patent which expired in 2016 (I wonder how they managed to get the patent granted, maybe US patent laws were different back then in 1996).
unsigned avg = a / 2 + b / 2 + a & b & 1;
Here, we are leaving the lowest bit in the addition and we make the necessary adjustment using carry from the lowest bit.
Also, note that this is a single cycle operation.
On a 64 bit processor, we can cast to a larger data type before performing the arithmetic operations.
auto avg = ((unsigned long)a + (unsigned long)b) / 2;
In C++ 20, we can also just use std::midpoint from the <numeric> header to skip over the implementation.
unsigned avg = std::midpoint(a, b);
Both std::midpoint and std::lerp were added in C++ 20. They were proposed in this paper, and although both of them are implemented in most compilers, you can check out this page to see whether they are supported by your compiler's standard library.
The last approach I will show you is known as SIMD within a register (SWAR)
unsigned avg = (a & b) + (a ^ b) / 2;
This might look strange but it can be explained pretty easily.
Note that, a & b are the bits which are common in both of them and since average of two equal numbers is the number itself, we add these common bits as they are. And, a ^ b are the bits which are only present in one of them, so we halve them before the addition is performed.
This error is often present in divide-and-conquer algorithms such as binary search and mergesort. And thus, we have to make sure our algorithm is fast enough to be used in time oriented algorithms like mergesort.
Nowadays, we have various tools to detect integer overflows, one of them is the built-in functions provided by the compiler.
For GCC, these functions can be found here, and for Clang, they can be found here. You can check out the documentation given in those links, specifically, we are concerned with :
This function takes three parameters, the first two operands are the two unsigned integers a and b, and the third operand is a pointer where the result of the addition is stored. If the stored result is equal to the mathematically correct (infinite precision) result, then the functions returns false, otherwise it returns true.
if (__builtin_uadd_overflow(a, b, &result))
std::cout << "Overflow\n";
Another tool that can help us in detecting overflows is the status register in the CPU.
For 64 bit x86 CPUs, it is the RFLAGS register and the APSR for the ARM Cortex-A architecture. Although there exists no function in C or C++ which allows us to access these registers, we can always use a little bit of inline assembly to do the same.
That will be enough for this post and thank you!
Computer Science, Algorithms, C++