取 C 中两个有符号数的平均值

Question

假设我们有 x 和 y，并且在 C 中都是有符号整数，我们如何找到两者之间最准确的平均值？

我更喜欢一个不利用任何机器/编译器/工具链特定工作的解决方案。

我想出的最好的方法是：(a / 2) + (b / 2) + !!(a % 2) * !!(b %2) 有没有更有效的解决方案准确的？快点？更简单吗？

如果我们先验地知道其中一个是否大于另一个怎么办？

谢谢。

D

---

编者注：请注意，当输入值接近 C int 类型的最大绝对界限时，OP 期望得到的答案不会受到整数溢出的影响。这在原始问题中没有说明，但在给出答案时很重要。

Answer 1

接受答案（4 年）后，

我期望函数 intaverage_int(int a, int b) 为：
1. 针对 a 和 b 的所有组合，在 [INT_MIN..INT_MAX] 的整个范围内进行操作。
2. 与 (a+b)/2 获得相同的结果，就像使用更广泛的数学一样。

当int2x 存在，@Santiago Alessandri 方法效果很好。

int avgSS(int a, int b) {
  return (int) ( ((int2x) a + b) / 2);
}

否则 @AProgrammer 的变体：
注意：不需要更广泛的数学。

int avgC(int a, int b) {
  if ((a < 0) == (b < 0)) {  // a,b same sign
    return a/2 + b/2 + (a%2 + b%2)/2;
  }
  return (a+b)/2;
}

具有更多测试的 解决方案，但没有 %

以下所有解决方案“有效”到 1 以内(a+b)/2 当没有发生溢出时，但我希望找到一个与所有 int< 匹配的 (a+b)/2 /代码>。

---

@Santiago Alessandri 只要 int 的范围小于 int 的范围，解决方案就可以工作。 code>long long - 通常就是这种情况。

((long long)a + (long long)b) / 2

---

@AProgrammer（接受的答案）大约有 1/4 的时间无法匹配 (a+b)/ 2..示例输入如 a == 1, b == -2

a/2 + b/2 + (a%2 + b%2)/2

---

@Guy Sirton，解决方案失败大约 1/8 的时间匹配 (a+b)/2。示例输入如 a == 1, b == 0

int sgeq = ((a<0)==(b<0));
int avg = ((!sgeq)*(a+b)+sgeq*(b-a))/2 + sgeq*a;

---

@R..，解决方案失败大约 1/4 的时间来匹配 (a+b)/2。示例输入如 a == 1, b == 1

return (a-(a|b)+b)/2+(a|b)/2;

---

@MatthewD，现在删除的解决方案失败大约 5/6 的时间匹配 (a+b)/2。输入示例，例如 a == 1, b == -2

unsigned diff;
signed mean;
if (a > b) {
    diff = a - b;
    mean = b + (diff >> 1);
} else {
    diff = b - a;
    mean = a + (diff >> 1);
}

Answer 2

如果 (a^b)<=0 你可以直接使用 (a+b)/2 而不必担心溢出。

否则，请尝试 (a-(a|b)+b)/2+(a|b)/2。 -(a|b) 的大小至少与 a 和 b 一样大，并且具有相反的符号，因此可以避免溢出。

我很快就这样做了，所以可能会出现一些愚蠢的错误。请注意，这里没有特定于机器的黑客。 所有行为完全由 C 标准决定，事实上它需要有符号值的补码、补码或符号数值表示，并指定按位运算符对逐位表示进行处理。 不，a|b 的相对大小取决于表示形式...

编辑： 您还可以使用 a+(ba)/2< /code> 当它们具有相同的符号时。请注意，这会偏向 a。您可以反转它并偏向 b。另一方面，如果我没有弄错的话，我上面的解决方案会偏向于零。

另一种尝试：一种标准方法是(a&b)+(a^b)/2。在二进制补码中，无论符号如何，它都可以工作，但我相信如果 a 和 b 具有相同的符号，它也可以在补码或符号量值中工作。介意检查一下吗？

Answer 3

编辑：由@chux修复的版本 - 恢复莫妮卡：

if ((a < 0) == (b < 0)) {  // a,b same sign
  return a/2 + b/2 + (a%2 + b%2)/2;
} else {
  return (a+b)/2;
}

---

原始答案（如果它没有被接受，我会删除它）。

a/2 + b/2 + (a%2 + b%2)/2

似乎是最简单的一种，符合对实现特征没有假设的要求（它依赖于 C99，它将 / 的结果指定为“向 0 截断”，而它依赖于 C90 的实现）。

它的优点是无需测试（因此无需昂贵的跳转），并且所有除法/余数均除以 2，因此编译器可以使用位旋转技术。

Answer 4

对于无符号整数，平均值是 (x+y)/2 的下限。但对于有符号整数，同样会失败。对于总和为奇数的整数，此公式失败，因为它们的下限比平均值小 1。

您可以在 Hacker's Delight 中阅读更多内容，第 2.5 节

计算 2 个有符号整数的平均值的代码，无需溢出是

int t = (a & b) + ((a ^ b) >> 1)
unsigned t_u = (unsigned)t
int avg = t + ( (t_u >> 31 ) & (a ^ b) )

我已经使用 Z3 SMT 求解器 检查了它的正确性

Answer 5

一些观察可能会有所帮助：

“最准确”对于整数来说不一定是唯一的。例如，对于 1 和 4，2 和 3 是同样“最准确”的答案。从数学上来说（不是 C 整数）：

(a+b)/2 = a+(b-a)/2 = b+(a-b)/2

让我们尝试将其分解：

• 如果 sign(a)!=sign(b) 那么 a+b 将不会溢出。这种情况可以通过比较二进制补码表示中的最高有效位来确定。
• 如果sign(a)==sign(b)，那么如果a大于b，(ab)不会溢出。否则(ba)不会溢出。编辑：实际上两者都不会溢出。

您到底想优化什么？不同的处理器架构可能有不同的最佳解决方案。例如，在代码中用 AND 替换乘法可能会提高性能。另外，在二进制补码架构中，您可以简单地（a & b & 1）。

我只是要扔掉一些代码，看起来不会太快，但也许有人可以使用和改进：

int sgeq = ((a<0)==(b<0));
int avg = ((!sgeq)*(a+b)+sgeq*(b-a))/2 + sgeq*a

Answer 6

我会这样做，将两者都转换为 long long（64 位有符号整数），将它们相加，这不会溢出，然后将结果除以 2：

((long long)a + (long long)b) / 2

如果您想要小数部分，请将其存储为双精度。

请务必注意，结果将适合 32 位整数。

如果您使用最高等级的整数，那么您可以使用：

((double)a + (double)b) / 2

Answer 7

该答案适合任意数量的整数：

    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