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

编辑：

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

哇！

编辑 2：Great discussion on Microsoft blog

Answer 1

以下方法避免了溢出，并且应该在不依赖于 non-standard 特征的情况下产生相当有效的组装 (example)：

    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 位，这可能是不必要的，因为编译器知道它们已被用于生成该值的任何先前指令清除。

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

add     rax, rcx
shr     rax

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

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

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

Efficient overflow-immune arithmetic mean in C/C++

c

c++

optimization

intrinsics

compiler-optimization