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

Question

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

\n

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

\n

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

\n

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

\n

脚注1：对于无符号整数，我们可以用两条指令来完成。尽管循环进位在 Intel CPU 上超过 1 uop，但这可能是最快的方法。但当计数仅为 1 时，只有一对。关于无符号均值的问答中的答案讨论了效率。

\n

add rdi, rsi\nrcr rdi, 1\n

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

\n

脚注 2：我指定了寄存器长度的有符号整数，这样我们就不能简单地用movsxdorcdqe指令对整数进行符号扩展。

\n

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

\n

add rdi, rsi\nsetge al\nsub al, 1          # CF = !(ge) = !(SF==OF)\nrcr rdi, 1         # shift CF into the top of (a+b)>>1\n

我认为更短的解决方案可能在于以某种方式组合中间两条指令，即执行CF \xe2\x86\x90 SF \xe2\x89\xa0 OF.

\n

我看过这个问题，但这不是特定于 x86 的，而且似乎没有一个答案可以编译成与我的解决方案一样好的结果。

\n

Answer 1

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

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

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

由于sar四舍五入到负无穷大，该算法的结果是：

作为奖励，对于随机输入，平均舍入误差为零。

在典型的 CPU 上它应该是 3 uops，延迟为 2 个周期，因为两者sar是独立的。

这里的“向上”总是朝向 +Inf，而不是围绕 0 对称。但是，对于 `avg(-3,-3)`，我们得到 `-2 + -2 + CF(1)`，所以我们得到了正确的结果`-3`。对于“avg(3,3)”，我们得到“1 + 1 + CF(1)”，它也是 3。因此添加 CF 的始终向上抵消算术右移的朝 -Inf 舍入。 (3认同)

Answer 2

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

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

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

请注意，可以使用未签名的例程来实现签名的例程，尽管通常正确解决溢出问题是一场噩梦。不过，您当前的解决方案在这方面似乎已经被破坏了。