Return to Question

I was extremely annoyed by the lengthy, edge-case-galore explanation of integer version of C++ standard library mindpoint implementation here, so I made my own simple 2's complement version. I present it for your judgement.

The general idea is to carry out a + (b-a)/2 in a wider singed integer that won't ever overflow. Say a and b are N bit integers. Consider them as imaginary singed (2's complement) N+1 bit integers. The obvious magic of 2's complement is that we can carry out addition/subtraction as usual, so first we obtain the lower N bits of the hypothetical N+1 bit difference,

Unsigned diff = Unsigned(b) - Unsigned(a);

working with unsigned type to avoid signed overflow UB. We don't really have the +1 bit, so just imagine sign extension also happens. We only care about lower N bits anyway since we know the final half difference has to fit there. Problem is - we can't do division in this straightforward way, so we have to branch, based on the sign of the final result.

• If N+1 bit difference was negative (highest/sign bit set), we jump through hoops:
  Negate/abs (2's complement approved as subtraction 0-diff).
  Unsigned negative_2x = -diff;
  Divide (it works cause sign bit is now guaranteed 0).
  negative_2x /= 2;
  Now we can fit this halfed difference back into our original N bit signed int, so we convert it back and negate to restore the original sign.
  Integer negative = -Integer(negative_2x);
  Converting first is important to avoid signed overflow UB again. If original Integer was unsigned this still works, since the wrapping behavior is consistent with 2's complement.

• Otherwise if difference was positive, it fully fit in N bits unsigned, and half of it should fit in signed, no hoops:
  Integer positive = diff / 2;

The actual branch looks like this to encourage conditional move, not that compilers care...

return a + (b < a ? negative : positive);

The code by itself with a primitive/stand-in function signature, for the purposes of copying into an IDE and compiling:

#include <type_traits>

template<typename Integer, typename Unsigned = std::make_unsigned_t<Integer>>
Integer midpoint(Integer a, Integer b)
{
    Unsigned diff = Unsigned(b) - Unsigned(a);

    Unsigned negative_2x = -diff;
    negative_2x /= 2;
    Integer negative = -Integer(negative_2x);

    Integer positive = diff / 2;

    return a + (b < a ? negative : positive);
}

Also available here, passes all the libstdc++ and libc++ unit tests for integers.

I was extremely annoyed by the lengthy, edge-case-galore explanation of integer version of C++ standard library mindpoint implementation here, so I made my own simple 2's complement version. I present it for your judgement.

The general idea is to carry out a + (b-a)/2 in a wider signed integer that won't ever overflow. Say a and b are N bit integers. Consider them as imaginary signed (2's complement) N+1 bit integers. The obvious magic of 2's complement is that we can carry out addition/subtraction as usual, so first we obtain the lower N bits of the hypothetical N+1 bit difference,

Unsigned diff = Unsigned(b) - Unsigned(a);

working with unsigned type to avoid signed overflow UB. We don't really have the +1 bit, so just imagine sign extension also happens. We only care about lower N bits anyway since we know the final half difference has to fit there. Problem is - we can't do division in this straightforward way, so we have to branch, based on the sign of the final result.

• If N+1 bit difference was negative (highest/sign bit set), we jump through hoops:
  Negate/abs (2's complement approved as subtraction 0-diff).
  Unsigned negative_2x = -diff;
  Divide (it works cause sign bit is now guaranteed 0).
  negative_2x /= 2;
  Now we can fit this halved difference back into our original N bit signed int, so we convert it back and negate to restore the original sign.
  Integer negative = -Integer(negative_2x);
  Converting first is important to avoid signed overflow UB again. If original Integer was unsigned this still works, since the wrapping behavior is consistent with 2's complement.

• Otherwise if difference was positive, it fully fit in N bits unsigned, and half of it should fit in signed, no hoops:
  Integer positive = diff / 2;

The actual branch looks like this to encourage conditional move, not that compilers care...

return a + (b < a ? negative : positive);

The code by itself with a primitive/stand-in function signature, for the purposes of copying into an IDE and compiling:

#include <type_traits>

template<typename Integer, typename Unsigned = std::make_unsigned_t<Integer>>
Integer midpoint(Integer a, Integer b)
{
    Unsigned diff = Unsigned(b) - Unsigned(a);

    Unsigned negative_2x = -diff;
    negative_2x /= 2;
    Integer negative = -Integer(negative_2x);

    Integer positive = diff / 2;

    return a + (b < a ? negative : positive);
}

Also available here, passes all the libstdc++ and libc++ unit tests for integers.

I was extremity annoyed by the lengthy, edge-case-galore explanation of integer version of C++ standard library mindpoint implementation here, so I made my own simple 2's complement version. I present it for your judgement, since senpai at libstdc++ didn't notice me T_T

The general idea is to carry out a + (b-a)/2 in a wider singed integer that won't ever overflow. Say a and b are N bit integers. Consider them as imaginary singed (2's complement) N+1 bit integers. The obvious magic of 2's complement is that we can carry out addition/subtraction as usual, so first we obtain the lower N bits of the hypothetical N+1 bit difference,

Unsigned diff = Unsigned(b) - Unsigned(a);

working with unsigned type to avoid signed overflow UB. We don't really have the +1 bit, so just imagine sign extension also happens. We only care about lower N bits anyway since we know the final half difference has to fit there. Problem is - we can't do division in this straightforward way, so we have to branch, based on the sign of the final result.

• If N+1 bit difference was negative (highest/sign bit set), we jump through hoops:
  Negate/abs (2's complement approved as subtraction 0-diff).
  Unsigned negative_2x = -diff;
  Divide (it works cause sign bit is now guaranteed 0).
  negative_2x /= 2;
  Now we can fit this halfed difference back into our original N bit signed int, so we convert it back and negate to restore the original sign.
  Integer negative = -Integer(negative_2x);
  Converting first is important to avoid signed overflow UB again. If original Integer was unsigned this still works, since the wrapping behavior is consistent with 2's complement.

• Otherwise if difference was positive, it fully fit in N bits unsigned, and half of it should fit in signed, no hoops:
  Integer positive = diff / 2;

The actual branch looks like this to encourage conditional move, not that compilers care...

return a + (b < a ? negative : positive);

The code by itself with a primitive/stand-in function signature, for the purposes of copying into an IDE and compiling:

#include <type_traits>

template<typename Integer, typename Unsigned = std::make_unsigned_t<Integer>>
Integer midpoint(Integer a, Integer b)
{
    Unsigned diff = Unsigned(b) - Unsigned(a);

    Unsigned negative_2x = -diff;
    negative_2x /= 2;
    Integer negative = -Integer(negative_2x);

    Integer positive = diff / 2;

    return a + (b < a ? negative : positive);
}

Also available here, passes all the libstdc++ and libc++ unit tests for integers.

I was extremely annoyed by the lengthy, edge-case-galore explanation of integer version of C++ standard library mindpoint implementation here, so I made my own simple 2's complement version. I present it for your judgement.

The general idea is to carry out a + (b-a)/2 in a wider singed integer that won't ever overflow. Say a and b are N bit integers. Consider them as imaginary singed (2's complement) N+1 bit integers. The obvious magic of 2's complement is that we can carry out addition/subtraction as usual, so first we obtain the lower N bits of the hypothetical N+1 bit difference,

Unsigned diff = Unsigned(b) - Unsigned(a);

working with unsigned type to avoid signed overflow UB. We don't really have the +1 bit, so just imagine sign extension also happens. We only care about lower N bits anyway since we know the final half difference has to fit there. Problem is - we can't do division in this straightforward way, so we have to branch, based on the sign of the final result.

• If N+1 bit difference was negative (highest/sign bit set), we jump through hoops:
  Negate/abs (2's complement approved as subtraction 0-diff).
  Unsigned negative_2x = -diff;
  Divide (it works cause sign bit is now guaranteed 0).
  negative_2x /= 2;
  Now we can fit this halfed difference back into our original N bit signed int, so we convert it back and negate to restore the original sign.
  Integer negative = -Integer(negative_2x);
  Converting first is important to avoid signed overflow UB again. If original Integer was unsigned this still works, since the wrapping behavior is consistent with 2's complement.

• Otherwise if difference was positive, it fully fit in N bits unsigned, and half of it should fit in signed, no hoops:
  Integer positive = diff / 2;

The actual branch looks like this to encourage conditional move, not that compilers care...

return a + (b < a ? negative : positive);

The code by itself with a primitive/stand-in function signature, for the purposes of copying into an IDE and compiling:

#include <type_traits>

template<typename Integer, typename Unsigned = std::make_unsigned_t<Integer>>
Integer midpoint(Integer a, Integer b)
{
    Unsigned diff = Unsigned(b) - Unsigned(a);

    Unsigned negative_2x = -diff;
    negative_2x /= 2;
    Integer negative = -Integer(negative_2x);

    Integer positive = diff / 2;

    return a + (b < a ? negative : positive);
}

Also available here, passes all the libstdc++ and libc++ unit tests for integers.

I was extremity annoyed by the lengthy, edge-case-galore explanation of integer version of C++ standard library mindpoint implementation here, so I made my own simple 2's complement version. I present it for your judgement, since senpai at libstdc++ didn't notice me T_T

The general idea is to carry out a + (b-a)/2 in a wider singed integer that won't ever overflow. Say a and b are N bit integers. Consider them as imaginary singed (2's complement) N+1 bit integers. The obvious magic of 2's complement is that we can carry out addition/subtraction as usual, so first we obtain the lower N bits of the hypothetical N+1 bit difference,

Unsigned diff = Unsigned(b) - Unsigned(a);

working with unsigned type to avoid signed overflow UB. We don't really have the +1 bit, so just imagine sign extension also happens. We only care about lower N bits anyway since we know the final half difference has to fit there. Problem is - we can't do division in this straightforward way, so we have to branch, based on the sign of the final result.

• If N+1 bit difference was negative (highest/sign bit set), we jump through hoops:
  Negate/abs (2's complement approved as subtraction 0-diff).
  Unsigned negative_2x = -diff;
  Divide (it works cause sign bit is now guaranteed 0).
  negative_2x /= 2;
  Now we can fit this halfed difference back into our original N bit signed int, so we convert it back and negate to restore the original sign.
  Integer negative = -Integer(negative_2x);
  Converting first is important to avoid signed overflow UB again. If original Integer was unsigned this still works, since the wrapping behavior is consistent with 2's complement.

• Otherwise if difference was positive, it fully fit in N bits unsigned, and half of it should fit in signed, no hoops:
  Integer positive = diff / 2;

The actual branch looks like this to encourage conditional move, not that compilers care...

auto overflew = b < a;
return a + (overflew ? negative : positive);

Full version here passes all the libstdc++ and libc++ unit tests for integers.

I was extremity annoyed by the lengthy, edge-case-galore explanation of integer version of C++ standard library mindpoint implementation here, so I made my own simple 2's complement version. I present it for your judgement, since senpai at libstdc++ didn't notice me T_T

The general idea is to carry out a + (b-a)/2 in a wider singed integer that won't ever overflow. Say a and b are N bit integers. Consider them as imaginary singed (2's complement) N+1 bit integers. The obvious magic of 2's complement is that we can carry out addition/subtraction as usual, so first we obtain the lower N bits of the hypothetical N+1 bit difference,

Unsigned diff = Unsigned(b) - Unsigned(a);

working with unsigned type to avoid signed overflow UB. We don't really have the +1 bit, so just imagine sign extension also happens. We only care about lower N bits anyway since we know the final half difference has to fit there. Problem is - we can't do division in this straightforward way, so we have to branch, based on the sign of the final result.

• If N+1 bit difference was negative (highest/sign bit set), we jump through hoops:
  Negate/abs (2's complement approved as subtraction 0-diff).
  Unsigned negative_2x = -diff;
  Divide (it works cause sign bit is now guaranteed 0).
  negative_2x /= 2;
  Now we can fit this halfed difference back into our original N bit signed int, so we convert it back and negate to restore the original sign.
  Integer negative = -Integer(negative_2x);
  Converting first is important to avoid signed overflow UB again. If original Integer was unsigned this still works, since the wrapping behavior is consistent with 2's complement.

• Otherwise if difference was positive, it fully fit in N bits unsigned, and half of it should fit in signed, no hoops:
  Integer positive = diff / 2;

The actual branch looks like this to encourage conditional move, not that compilers care...

return a + (b < a ? negative : positive);

The code by itself with a primitive/stand-in function signature, for the purposes of copying into an IDE and compiling:

#include <type_traits>

template<typename Integer, typename Unsigned = std::make_unsigned_t<Integer>>
Integer midpoint(Integer a, Integer b)
{
    Unsigned diff = Unsigned(b) - Unsigned(a);

    Unsigned negative_2x = -diff;
    negative_2x /= 2;
    Integer negative = -Integer(negative_2x);

    Integer positive = diff / 2;

    return a + (b < a ? negative : positive);
}

Also available here, passes all the libstdc++ and libc++ unit tests for integers.