C/C++中高效的溢出免疫算术平均值 [英] Efficient overflow-immune arithmetic mean in C/C++

问题描述

两个无符号整数的算术平均值定义为：

mean = (a+b)/2

在C/C++中直接实现它可能会溢出并产生错误的结果。正确的实现可以避免这种情况。一种编码方式可能是：

mean = a/2 + b/2 + (a%2 + b%2)/2

但这会使用典型的编译器生成相当多的代码。在汇编程序中，这通常可以更高效地完成。例如，x86可以通过以下方式做到这一点(汇编伪代码，我希望您明白这一点)：

ADD a,b   ; addition, leaving the overflow condition in the carry bit
RCR a,1   ; rotate right through carry, effectively a division by 2

在这两条指令之后，结果在a中，剩余的除法在进位位中。如果需要正确的舍入，则第三条ADC指令必须将进位加到结果中。

请注意，使用的是RCR指令，它通过进位循环寄存器。在我们的例子中，它是旋转一个位置，因此前一个进位成为寄存器中的最高有效位，而新的进位保存寄存器中的前一个LSB。MSVC似乎甚至没有为此指令提供内部函数。

有没有一种已知的C/C++模式可以被优化编译器识别，从而生成如此高效的代码？或者，更广泛地说，有没有一种合理的方法来在C/C++源代码级别编程，以便编译器使用进位位来优化生成的代码？

编辑：

关于std::midpoint：https://www.youtube.com/watch?v=sBtAGxBh-XI

的1小时讲座

哇！

EDIT2：Great discussion on Microsoft blog

推荐答案

以下方法可避免溢出，并应在不依赖非标准功能的情况下产生相当高效的汇编(example)：

    mean = (a&b) + (a^b)/2;

这篇关于C/C++中高效的溢出免疫算术平均值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！