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

user_373730 0
Viewed 13533

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?

unsigned-integer math c++
10 Answers

In C++20, you can use std::midpoint:

template <class T>
constexpr T midpoint(T a, T b) noexcept;

The paper P0811R3 that introduced std::midpoint recommended this snippet (slightly adopted to work with C++11):

#include <type_traits>

template <typename Integer>
constexpr Integer midpoint(Integer a, Integer b) noexcept {
  using U = std::make_unsigned<Integer>::type;
  return a>b ? a-(U(a)-b)/2 : a+(U(b)-a)/2;
}

For completeness, here is the unmodified C++20 implementation from the paper:

constexpr Integer midpoint(Integer a, Integer b) noexcept {
  using U = make_unsigned_t<Integer>;
  return a>b ? a-(U(a)-b)/2 : a+(U(b)-a)/2;
}
user_7835100
user_8139180
Related