在x86汇编中求两个有符号整数平均值的最快方法？

Question

假设我们有两个寄存器长度^{2有符号1整数，例如a和b。我们想要计算值，向上、向下、接近零或远离零，无论哪种方式更容易（即，我们不关心取整方向）。}

结果是另一个寄存器长度有符号整数（很明显，平均值必须在寄存器长度有符号整数的范围内）。

执行此计算的最快方法是什么？

您可以选择两个整数最初在哪个寄存器中，以及平均值最终在哪个寄存器中。

脚注1：对于无符号整数，我们可以在两条指令中完成。这可能是最快的方式，尽管在Intel CPU上通过进位旋转的速度超过1 uop。但是只有一对，当计数只有1时。一个问题的答案

add rdi, rsi
rcr rdi, 1

这两个数字从rdi和rsi开始，平均值以rdi结束。但对于有符号数字，-13将设置CF，并将a旋转到符号位。没有给出正确答案。

脚注2：我指定了寄存器长度有符号整数，因此我们不能简单地使用movsxd或cdqe指令对扩展整数进行签名。

我找到的最接近解决方案使用了四条指令，其中一条是rcr，在Intel上是3个UOP，在AMD Zen上是1个(https://uops.info/):

add rdi, rsi
setge al
sub al, 1
rcr rdi, 1

我认为更短的解决方案可能在于以某种方式组合中间的两条指令，即执行CF←SF≠OF。

我见过这个问题，但这不是x86特有的，而且没有一个答案像我的解决方案那样好。




Answer 1

作为外部答案，考虑pavg指令系列。

我说“外面”，因为这可能是你不能接受的。它假设值是无符号8位或16位，并且在SSE寄存器中，这当然也需要SSE。我之所以提到它，主要是因为它是x86的涂油等效于其他ISA中的平均指令。

在它的辩护中，SSE现在无处不在，甚至在x86-64上也有保证。此外，该指令是1个周期，如果您愿意，实际上可以同时执行4个周期。最重要的是，与原始解决方案不同，它还可以正确处理溢出问题。

请注意，可以使用无符号例程来实现有符号例程，尽管通常正确解释溢出问题是一场噩梦。然而，你目前的解决方案似乎已经在这方面被打破了。

Answer 2

根据我们如何解释您宽松的舍入要求，以下内容可能是可以接受的：

sar rdi, 1
sar rsi, 1
adc rdi, rsi

试戴锁销

这有效地将两个输入除以2，添加结果，如果rsi是奇数，则再添加1。（请记住，sar根据移出的最后一位设置进位标志。）

由于sar舍入为负无穷大，因此该算法的结果是：

>

如果rdi和rsi都是偶数或奇数，则完全正确

如果rdi为奇数，rsi为偶数，则向下舍入（朝向负无穷大）

如果rdi是偶数而rsi是奇数，则向上舍入（朝向加无穷大）

另外，对于随机输入，平均舍入误差为零。

一个典型的CPU上应该有3个UOP，延迟为2个周期，因为两个sar是独立的。