4
\$\begingroup\$

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.

\$\endgroup\$
18
  • 1
    \$\begingroup\$ Welcome to the Code Review Community. We can only review code that is included in the question. While we can use repositories for reference, there just isn't enough code in the question to review and that makes the question off-topic. Please read How do I ask a good question? in the help center. Please note that if the code isn't working as expected that also makes the question off-topic. \$\endgroup\$
    – pacmaninbw
    Nov 26 '20 at 0:25
  • 3
    \$\begingroup\$ see, those 7 lines in that post don't look like the 7 lines in your IDE of choice. We really don't want you to sprinkle the code under review in between an extensive explanation of what the code does. Instead we want to see the code and an explanation for it. Taking a look at other questions on the site (that have not been closed) hopefully gives you an idea how this community prefers questions. I'd also avoid "wrong" in the question title, if only because people could easily get the wrong idea about what you're actually asking for... \$\endgroup\$
    – Vogel612
    Nov 26 '20 at 20:21
  • 2
    \$\begingroup\$ Yes, we want to see the full code, we want function signatures, we want context. If you think each line needs a separate explanation, put it in a code comment. And definitely don't put "what's wrong" in the title of your question. And links can carry additional information that is not necessary but we cannot consider them a legitimate part of your question. We cannot know if the link is dead or provides different information by tomorrow... \$\endgroup\$
    – slepic
    Nov 27 '20 at 5:28
  • 2
    \$\begingroup\$ Somebody here does not understand, that's for sure. Look, you can keep your own truth and get rejected by the community or you accept the community truth and post it the way the community wants it. Easy as that. \$\endgroup\$
    – slepic
    Nov 28 '20 at 6:49
  • 2
    \$\begingroup\$ "the code is there in its entirety" that's disputable. If I cut a picture into pieces and toss those pieces into a cup of tea, then I give you the tea and say "nice picture, huh?" even if you were an arts expert, you wouldn't be very confident answering that one, would you? We want a specification and its implementation - the code, possibly decorated with some explanatory comments. Rather than an essay with fragments of code in it. \$\endgroup\$
    – slepic
    Nov 28 '20 at 13:55
5
\$\begingroup\$

Naming things

The variable names are not very clear. I assume the _2x stands for "2's complement" instead for "times 2", but for someone who doesn't know the context, it will be hard to follow. I'm not sure what the best way to name them is though, but as shown below you can avoid the issue altogether.

Don't use a template parameter for a derived type

If you make Unsigned a template parameter, it means someone can override it to something nonsensical. If you want to have a named type that is a derivative of another type, use using inside the function body:

template<typename Integer>
Integer midpoint(Integer a, Integer b)
{
    using Unsigned = std::make_unsigned_t<Integer>;
    ...
}

Simplifying the code

Most of the temporary variables can be removed. I would keep the variable diff, as it is the most important one where the casts are essential, and since it is used twice:

template<typename Integer>
Integer midpoint(Integer a, Integer b)
{
    using Unsigned = std::make_unsigned_t<Integer>;
    Unsigned diff = Unsigned(b) - Unsigned(a);
    return a + (b < a ? -Integer(Unsigned(-diff) / 2) : Integer(diff / 2));
}

The return expression is still reasonably short, and I don't think any information was lost. Adding some comments explaining why the casts are necessary would be helpful though.

\$\endgroup\$
9
  • \$\begingroup\$ Hm now I wonder now if it should be -Integer(-diff / 2) or not, as you mentioned that this might be UB otherwise, but would it still be UB with C++20's mandatory two's complement signed integers? \$\endgroup\$
    – G. Sliepen
    Nov 29 '20 at 14:50
  • \$\begingroup\$ I have Unsigned as template parameter to use the function for types other than the fundamental integers, without specializing std::make_unsigned_t, but that is out of context here, I wanted to discuss the implementation only, I was "forced" to include the signature. In context of standard spec of midpoint, I can criticize your signature as well to no end. \$\endgroup\$
    – namark
    Nov 29 '20 at 16:38
  • \$\begingroup\$ The _2x does indeed mean 2 times, indicating that we are dealing with a number that is twice the range of our original (+1 bit), and only after properly halfing it can we assign it back to the original type. One should be familiar with 2's compliment to understand this code yes, but I think that's better than consider numerous edge cases. You might have not concidered char or short, and promotion rules, since you code is failing some test cases. You can check out the repo I linked, modify the midpoint there and run make test see the details. \$\endgroup\$
    – namark
    Nov 29 '20 at 16:43
  • \$\begingroup\$ It is possible that a single cast can be eliminated thanks to C++20's two's complement, but there are a lot more casts happening there, mainly to combat pesky promotion. I wonder what things might look like with something like safe_numerics library employed here, and what the codegen would be. \$\endgroup\$
    – namark
    Nov 29 '20 at 16:47
  • 1
    \$\begingroup\$ I tried with gcc on x86_64, are you sure the assembly is the same for short and char? For example one of the failing cases looks like this midpoint(limits::max(), limits::min()) == T( 0) where T is singed char/short and limits is std::numeric_limits<T>. \$\endgroup\$
    – namark
    Nov 29 '20 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.