C/C++ 中高效的防溢出算术平均值

Question

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

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++ 源代码级别进行编程，以便编译器使用进位位来优化生成的代码？

编辑：

1 小时的讲座std::midpoint：https://www.youtube.com/watch ?v=sBtAGxBh-XI

哇！

EDIT2：微软博客上的精彩讨论

Answer 1

以下方法可以避免溢出，并且应该会产生相当有效的组装（示例），而不依赖于非标准功能：

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

Answer 2

有三种典型的方法可以计算平均值而不会溢出，其中一种仅限于 uint32_t（在 64 位架构上）。

// average "SWAR" / Montgomery
uint32_t avg(uint32_t a, uint32_t b) {
   return (a & b) + ((a ^ b) >> 1);
}

// in case the relative magnitudes are known
uint32_t avg2(uint32_t min, uint32_t max) {
  return min + (max - min) / 2;
}
// in case the relative magnitudes are not known
uint32_t avg2_constrained(uint32_t a, uint32_t b) {
  return a + (int32_t)(b - a) / 2;
}

// average increase width (not applicable to uint64_t)
uint32_t avg3(uint32_t a, uint32_t b) {
   return ((uint64_t)a + b) >> 1;
}

两种架构中 clang 对应的汇编程序序列是

avg(unsigned int, unsigned int)
    mov     eax, esi
    and     eax, edi
    xor     esi, edi
    shr     esi
    add     eax, esi

avg2(unsigned int, unsigned int)
    sub     esi, edi
    shr     esi
    lea     eax, [rsi + rdi]

avg3(unsigned int, unsigned int)
    mov     ecx, edi
    mov     eax, esi
    add     rax, rcx
    shr     rax

与

avg(unsigned int, unsigned int)         
    and     w8, w1, w0
    eor     w9, w1, w0
    add     w0, w8, w9, lsr #1
    ret
avg2(unsigned int, unsigned int)
    sub     w8, w1, w0
    add     w0, w0, w8, lsr #1
    ret
avg3(unsigned int, unsigned int):                                       
    mov     w8, w1
    add     x8, x8, w0, uxtw
    lsr     x0, x8, #1
    ret

在这三个版本中，avg2也将在 ARM64 中执行，因为使用进位标志的最佳序列 - 并且很可能也会avg3执行，请注意mov w8,w1用于清除顶部 32 位，这可能是不必要的编译器知道它们已被用于生成该值的任何先前指令清除。

Intel 版本的 也可以做出类似的声明avg3，在最佳情况下，它会编译为仅两个有意义的指令：

add     rax, rcx
shr     rax

在线比较请参见https://godbolt.org/z/5TMd3zr81 。

“SWAR”/蒙哥马利版本通常仅在尝试计算打包为单个（大）整数的多个平均值时才合理，在这种情况下，完整公式包含最高位的位位置的掩码：return (a & b) + (((a ^ b) >> 1) & ~kH;。