45

仅使用整数数学，我想在 C++ 中“安全地”平均两个无符号整数。

我所说的“安全”是指避免溢出（以及任何其他可以想到的）。

例如，平均200和5000很容易：

unsigned int a = 200;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2600 as intended

但在4294967295和5000的情况下：

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2499 instead of 2147486147

我想出的最好的是：

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a / 2) + (b / 2); // Equals: 2147486147 as expected

有没有更好的方法？

4

10 回答 10

55

您的最后一种方法似乎很有希望。您可以通过手动考虑 a 和 b 的最低位来改进它：

unsigned int average = (a / 2) + (b / 2) + (a & b & 1);

如果 a 和 b 都是奇数，这将给出正确的结果。

于 2010-09-28T19:47:34.747 回答
29

如果您提前知道哪个更高，那么一种非常有效的方法是可能的。否则，您最好使用其他策略之一，而不是有条件地交换使用它。

unsigned int average = low + ((high - low) / 2);

这是一篇相关文章：http: //googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

于 2010-09-28T19:47:30.863 回答
18

如果两个数字都是奇数，例如 5 和 7，则您的方法不正确，平均值为 6，但您的方法 #3 返回 5。

试试这个：

average = (a>>1) + (b>>1) + (a & b & 1)

仅使用数学运算符：

average = a/2 + b/2 + (a%2) * (b%2)
于 2010-09-28T19:48:11.523 回答
9

如果您不介意一点 x86 内联汇编（GNU C 语法），您可以利用 supercat 的建议，在 add 后使用rotate-with-carry将完整 33 位结果的高 32 位放入寄存器.

当然，您通常应该介意使用 inline-asm，因为它会破坏一些优化（https://gcc.gnu.org/wiki/DontUseInlineAsm）。但无论如何我们都走了：

// works for 64-bit long as well on x86-64, and doesn't depend on calling convention
unsigned average(unsigned x, unsigned y)
{
    unsigned result;
    asm("add   %[x], %[res]\n\t"
        "rcr   %[res]"
        : [res] "=r" (result)   // output
        : [y] "%0"(y),  // input: in the same reg as results output.  Commutative with next operand
          [x] "rme"(x)  // input: reg, mem, or immediate
        :               // no clobbers.  ("cc" is implicit on x86)
    );
    return result;
}

在我尝试的情况下，告诉编译器 args 是可交换的%修饰符实际上并没有帮助更好的 asm，调用函数时 y 是常量或指针 deref（内存操作数）。可能对输出操作数使用匹配约束会破坏这一点，因为您不能将它与读写操作数一起使用。

正如您在 Godbolt 编译器资源管理器中看到的那样，它可以正确编译，我们将操作数更改为 的版本也是如此unsigned long，具有相同的内联 asm。但是，clang3.9 把它弄得一团糟，并决定使用约束"m"选项"rme"，因此它存储到内存并使用内存操作数。

RCR-by-one 并不算太慢，但在 Skylake 上仍然是 3 uops，有 2 个周期延迟。在 RCR 具有单周期延迟的 AMD CPU 上非常棒。（来源：Agner Fog 的指令表，另请参阅标记 wiki 以获取 x86 性能链接）。它仍然比@sellibitze 的版本好，但比@Sheldon 的顺序依赖版本差。（参见 Godbolt 上的代码）

但请记住，inline-asm 会破坏诸如常量传播之类的优化，因此在这种情况下，任何纯 C++ 版本都会更好。

于 2010-09-28T21:19:28.467 回答
9

而正确的答案是……

(A&B)+((A^B)>>1)
于 2013-02-14T21:53:46.907 回答
4

你所拥有的很好，它会声称 3 和 3 的平均值是 2。我猜你不想要那个；幸运的是，有一个简单的解决方法：

unsigned int average = a/2 + b/2 + (a & b & 1);

在两个部门都被截断的情况下，这只会提高平均值。

于 2010-09-28T19:48:03.467 回答
2

如果代码用于嵌入式微，如果速度很关键，汇编语言可能会有所帮助。在许多微控制器上，加法的结果自然会进入进位标志，并且存在将其移回寄存器的指令。在 ARM 上，平均操作（寄存器中的源和目标）可以在两条指令中完成；任何等效的 C 语言都可能产生至少 5 个，并且可能比这更多。

顺便说一句，在字长较短的机器上，差异可能更大。在 8 位 PIC-18 系列上，平均两个 32 位数字需要 12 条指令。进行移位、加法和校正，每次移位需要 5 条指令，加法需要 8 条指令，加法需要 8 条指令，校正需要 8 条指令，因此需要 26 条指令（不是 2.5 倍的差异，但绝对值可能更重要）。

于 2010-09-28T20:37:57.553 回答
2

在 C++20 中，您可以使用std::midpoint：

template <class T>
constexpr T midpoint(T a, T b) noexcept;

介绍的论文P0811R3std::midpoint推荐了这个片段（略微采用 C++11）：

#include <type_traits>

template <typename Integer>
constexpr Integer midpoint(Integer a, Integer b) noexcept {
  using U = std::make_unsigned<Integer>::type;
  return a>b ? a-(U(a)-b)/2 : a+(U(b)-a)/2;
}

为了完整起见，这里是论文中未经修改的 C++20 实现：

constexpr Integer midpoint(Integer a, Integer b) noexcept {
  using U = make_unsigned_t<Integer>;
  return a>b ? a-(U(a)-b)/2 : a+(U(b)-a)/2;
}
于 2019-11-05T20:46:45.183 回答
-3 
    int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    decimal avg = 0;
    for (int i = 0; i < array.Length; i++){
        avg = (array[i] - avg) / (i+1) + avg;
    }

预计此测试的 avg == 5.0

于 2016-12-22T21:59:35.723 回答
-4

(((a&b << 1) + (a^b)) >> 1)也是一个不错的方法。

礼貌：http ://www.ragestorm.net/blogs/?p=29

于 2012-03-12T03:24:37.033 回答