It is kind of sad that not a single compiler implemented an optimal template specialization for std::midpoint.

Lockalsays:

Update: after reading cppreference now I see why: unlike optimized versions, std::midpoint provides very specific requirements for rounding, which are not supported by optimized versions.

Peter Boossays:

(int)(x + y)*.5

Stefan Kanthaksays:

EVERY properly written optimising compiler SHOULD emit code like

ADD RDI, RSI
RCR RDI, 1
MOV RAX, RDI

for this function.
If the target processor lacks the equivalent of the RCR (Rotate through carry right) instruction, but has a ROR (Rotate right) instruction, it can emit

RCR is an appealing solution but, on some processors, it is significantly more expensive than a simple shift.

Stefan Kanthaksays:

That’s the other reason why I mentioned to substitute it by ADC/ROR
ALSO: RCR is (if available) ALWAYS less expensive than the “pure” C formula/expression.

Sergei Sitnikovsays:

I think the example with 1 and 9223372036854775807 doesn’t demonstrate the problem: the problem is negative numbers, otherwise one can always do (uint) (x + y) >> 1.

If you only have positive integers, and you are using a two’s complement signed type, then I agree that you can always work around overflows with relative ease. I did not make this assumption.

Johnsays:

Actually, it still contains a possible overflow. You need to cast before the addition.

Sergei Sitnikovsays:

It doesn’t matter, actually. The addition works exactly the same for signed and unsigned types in two’s complement representation. The cast is needed to perform the unsigned bit shift which doesn’t preserve the sign (unlike the signed shift). In some sense the signed addition of non-negative values overflows to the sign bit, then we interpret the result as unsigned and do the unsigned division by 2.

$ swift repl 130
Welcome to Apple Swift version 5.7.2 (swiftlang-5.7.2.135.5 clang-1400.0.29.51).
Type :help for assistance.
1> 9223372036854775807+1
expression failed to parse:
error: repl.swift:1:20: error: arithmetic operation '9223372036854775807 + 1' (on type 'Int') results in an overflow
9223372036854775807+1
~~~~~~~~~~~~~~~~~~~^~

You may say that the overflow, if it is not trapped, may be ignored, and you will be right because modern C/C++ and most other systems rely on two’s complement. However, it is still, by definition, an overflow.

Sergei Sitnikovsays:

You are right guys. Today I learned that signed integer overflow behavior is undefined in C(++). Sorry for inconvenience.

moonchildsays:`((x^y)>>1) + (x&y)`

is 4 operations. Whereas`x + (y-x)>>1`

is only 3 operations (and has the same span). Am I missing something?moonchildsays:nevermind, the given algorithms are commutative

Qsays:`y-x` can overflow when operating on signed integers, which is UB is C/C++.

BartekFsays:you can also compare it with a C++20’s addition: std::midpoint from

Champok Dassays:Just linking to the various implementations of std::midpoint in various compilers

GCC – https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/std/numeric;h=0f1f26cd0c456f9bd1eb2fd6b2e7fd686a8a50e6;hb=refs/heads/trunk#l206

LLVM Clang – https://github.com/llvm/llvm-project/blob/main/libcxx/include/__numeric/midpoint.h

MSVC STD – https://github.com/microsoft/STL/blob/main/stl/inc/numeric#L651

Lockalsays:It is kind of sad that not a single compiler implemented an optimal template specialization for std::midpoint.

Lockalsays:Update: after reading cppreference now I see why: unlike optimized versions, std::midpoint provides very specific requirements for rounding, which are not supported by optimized versions.

Peter Boossays:(int)(x + y)*.5

Stefan Kanthaksays:EVERY properly written optimising compiler SHOULD emit code like

for this function.

If the target processor lacks the equivalent of the RCR (Rotate through carry right) instruction, but has a ROR (Rotate right) instruction, it can emit

instead.

Daniel Lemiresays:RCR is an appealing solution but, on some processors, it is significantly more expensive than a simple shift.

Stefan Kanthaksays:That’s the other reason why I mentioned to substitute it by ADC/ROR

ALSO: RCR is (if available) ALWAYS less expensive than the “pure” C formula/expression.

Sergei Sitnikovsays:I think the example with 1 and 9223372036854775807 doesn’t demonstrate the problem: the problem is negative numbers, otherwise one can always do (uint) (x + y) >> 1.

Daniel Lemiresays:If you only have positive integers, and you are using a two’s complement signed type, then I agree that you can always work around overflows with relative ease. I did not make this assumption.

Johnsays:Actually, it still contains a possible overflow. You need to cast before the addition.

Sergei Sitnikovsays:It doesn’t matter, actually. The addition works exactly the same for signed and unsigned types in two’s complement representation. The cast is needed to perform the unsigned bit shift which doesn’t preserve the sign (unlike the signed shift). In some sense the signed addition of non-negative values overflows to the sign bit, then we interpret the result as unsigned and do the unsigned division by 2.

Daniel Lemiresays:That’s still an overflow though.

You may say that the overflow, if it is not trapped, may be ignored, and you will be right because modern C/C++ and most other systems rely on two’s complement. However, it is still, by definition, an overflow.

Sergei Sitnikovsays:You are right guys. Today I learned that

signedinteger overflow behavior is undefined in C(++). Sorry for inconvenience.Norbert Juffasays:For historical context: The first publicly stated instance of the second formula that I am aware of appeared in a post by Peter L. Montgomery in newsgroup comp.arch on 2000/02/11; see

https://groups.google.com/d/msg/comp.arch/gXFuGZtZKag/_5yrz2zDbe4J:

”

If XOR is available, then this can be used to average

two unsigned variables A and B when the sum might overflow:

(A+B)/2 = (A AND B) + (A XOR B)/2

“