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

Question

假设我们有两个寄存器长度的有符号整数，例如a和b。 我们想要计算值(a + b) / 2，无论是向上舍入、向下舍入、朝零舍入还是远离零，以任何一种方式都可以(即我们不关心舍入方向)。

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

如何最快地执行此计算？

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

注1：对于无符号整数，我们可以用两条指令完成。 这可能是最快的方法，尽管在Intel CPU上，通过旋转需要超过1个uop。 但是当计数只有1时，只需要几个。 在有关无符号平均数的Q&A上An answer讨论了效率。

add rdi, rsi
rcr rdi, 1

两个数字分别在rdi和rsi寄存器中，平均数存储在rdi寄存器中。但对于带符号的数字，-1 + 3会设置CF标志，并将1旋转到符号位，导致未给出正确答案+1。

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

---

我接近解决方案的方法需要使用四条指令，其中一条是rcr指令，在英特尔处理器上需要3个微操作，在AMD Zen上只需要1个(https://uops.info/)：

add rdi, rsi
setge al
sub al, 1          # CF = !(ge) = !(SF==OF)
rcr rdi, 1         # shift CF into the top of (a+b)>>1

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

我看过这个问题，但那并非x86特定，并且没有一个答案似乎像我的方案一样好。

- Bernard

---

从rdi = -1和rsi = 3开始尝试。执行add rdi, rsi指令将设置CF标志位，并通过rcr rdi, 1指令旋转到rdi的符号位，导致结果为负数。但正确答案是1。 - Bernard

使用 RAX 替代 RDI 的 Hrm（汇编指令）意思是：将 RAX 寄存器中的值符号扩展到 RDX 和 RAX 中，将 RSI 加到 RAX 中，并将进位标志加到 RDX 中，然后将 RDX 中的值向右移动一位，将结果放回 RAX 中。 - Brendan

@NateEldredge 我认为在你的解决方案中将 add 更改为 adc 会使其稍微好一些，但存在某种不一致的舍入。 - Bernard

@Bernard：在英特尔主流CPU上，使用立即数进行SHRD操作速度很快，但在Alder Lake E核心上则是一场灾难（根据https://uops.info/测试，15个uops，13.6个周期的吞吐量）。在Zen2上只有6个uops，3个周期的吞吐量和延迟，因此只适用于英特尔Sandybridge系列。相比之下，RCR-by-1在英特尔上只需要3个uops，在AMD上只需要1个uop。因此，它的最坏情况要好得多。（使用除1以外的计数的RCR操作是可怕的。） - Peter Cordes

顺便提一下，setge rax 这样的东西不存在；你必须使用 8 位寄存器。 - Nate Eldredge

Answer 1

根据您宽松的四舍五入要求的理解，以下内容可能可以接受：

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

点此试用godbolt

该算法有效地将两个输入数都除以2，然后将它们的商相加，如果rsi是奇数，则再加1。（请记住，sar指令会根据最后一位移出的比特位设置进位标志。）

由于sar指令向下取整，所以该算法的结果为：

• 如果rdi和rsi均为偶数或者均为奇数，则完全正确；

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

• 如果rdi为偶数且rsi为奇数，则向上舍入（朝正无穷方向）。

作为附加赠品，对于随机输入，平均舍入误差为零。

在典型CPU上，该算法应该需要3个微操作，两个sar指令之间的延迟为2个周期。

- Nate Eldredge

---

这里的“up”始终指向正无穷，而不是围绕0对称。但是，对于avg（-3，-3），我们得到-2 + -2 + CF(1)，因此我们得到正确的-3。对于avg（3，3），我们得到1 + 1 + CF(1)，这也是3。因此，添加CF的始终向上作用抵消了算术右移的向负无穷舍入。 - Peter Cordes

@PeterCordes 这样的东西有用吗？ lea eax，[edi + esi] shr eax，1 - vengy

对于已知不会溢出的无符号输入，是的。即那些已经从31位或更窄的位进行了零扩展。（除非你不使用32位地址大小与LEA，你会使用lea eax，[rdi + rsi]来避免地址大小前缀）。但是这个问题和答案是关于可能为负数的全范围有符号输入。所以即使sar eax，1也是不够的。 - Peter Cordes

目前看来这是唯一更快的解决方案，但缺点是操作不可交换。 - Bernard

Answer 2

作为外部解决方案，考虑使用 pavg 指令族。

我之所以说“外部”，是因为这可能不符合您的要求。该指令假设值为无符号8位或16位，并在SSE寄存器中，这当然也需要SSE。我主要提到它，因为它是x86中类似于其他ISA中平均指令的指定等价指令。

值得一提的是，SSE现在已经普及，甚至在x86-64上也有保证。此外，该指令只需1个周期，如果您愿意，实际上可以同时执行4个。最重要的是，与您原来的解决方案不同，它还可以正确处理溢出问题。

请注意，可以使用无符号例程来实现有符号例程，尽管通常正确地处理溢出问题是一场噩梦。尽管如此，您当前的解决方案似乎已经存在此类问题。

- imallett

---

你可以尝试通过添加128（即翻转高位）来将有符号的值范围移动到无符号的范围吗？因此，使用set1_epi8（0x80）pxor两个输入，然后使用pavgb命令进行平均，并将结果再次使用pxor命令返回到有符号的范围内。我期望它可以在接近溢出边界时工作，因为pavgb / pavgw可以实现这一点。如果您想要一个32位操作数大小的向量版本的该技巧，那么还可以使用其他不依赖于进位的无符号舍入位运算。但是，对于单个标量平均值，从GP整数寄存器传输数据到XMM再返回通常不值得，特别是对于带符号数字。 - Peter Cordes

@PeterCordes 我无法评论如何使用有符号数的算法；这种事情非常难以正确处理，而且现在已经是凌晨2点了。是的，假设您已经在XMM寄存器中了。实际上，启发我回答的是最近一篇图像处理论文，其中这个方法被用于获得胜利；通过在整个图像上执行此操作，可以获得很多并行性，并且图像通常是8位无符号的，因此它基本上是一个完美的用例。 - geometrian

@Bernard 如果你有很多8/16位整数，那么这将会更快，因为它可以同时进行多个加法。 - phuclv

@Bernard 为了澄清，反对意见是你的解决方案无法正确处理溢出，主要是因为当 add 指令溢出时，可能会产生错误的结果。（这似乎也已经在问题评论中被注意到和讨论了。） - geometrian

关于性能方面，请注意，如果数据来自内存（很可能），您可以将其加载到SSE寄存器中，而不是整数寄存器中，这样对于标量也应该更快（尽管如果您需要后续的通用整数操作，则可能需要将其移出SSE，使其在性能上仅略有等价）。当然，我们应该通过分析/静态分析这些直觉来更精确地了解。 - geometrian