13

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

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

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

如果我们先验地知道一个比另一个大怎么办？

谢谢。

D

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

4

7 回答 7

9

接受答案后（4 年）

我希望该功能int average_int(int a, int b)能够： 1. 在和的所有组合
的整个范围内工作。 2. 与 具有相同的结果，就像使用更广泛的数学一样。[INT_MIN..INT_MAX]ab
(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;
}

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

以下所有解决方案“工作”到 (a+b)/2没有发生溢出时的 1 以内，但我希望找到一个与(a+b)/2所有int.

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

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

@AProgrammer，接受的答案，大约有 1/4 的时间失败 match (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);
}
于 2015-04-23T20:55:00.797 回答
3

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

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

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

编辑：a+(b-a)/2当它们具有相同的标志时，您也可以使用。请注意，这将偏向a. 您可以将其反转并偏向b. 另一方面，如果我没记错的话，我上面的解决方案会偏向零。

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

于 2011-04-18T00:53:58.923 回答
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，因此编译器可以使用位旋转技术。

于 2011-04-18T09:29:15.620 回答
1

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

“最准确”对于整数不一定是唯一的。例如，对于 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
于 2011-04-18T02:46:55.060 回答
1

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

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

计算2个有符号整数的平均值而不溢出的代码是

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

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

于 2016-03-16T20:56:38.150 回答
-1

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

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

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

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

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

((double)a + (double)b) / 2
于 2011-04-18T00:54:10.300 回答
-2

这个答案适合任意数量的整数：

    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-22T22:08:27.737 回答