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

Question

让我们说我们有x和y,两者都是C中的有符号整数,我们如何找到两者之间最准确的平均值？

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

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

如果我们知道一个是否比另一个先验大？

谢谢.

d

---

编者注:请注意,当输入值接近C int类型的最大绝对边界时,OP需要不受整数溢出影响的答案.这在原始问题中没有说明,但在给出答案时很重要.

Answer 1

接受答复后(4年)

我期望的功能int average_int(int a, int b)来:
在整个范围1.工作[INT_MIN..INT_MAX]进行组合a和b.
2.有相同的结果(a+b)/2,好像使用更广泛的数学.

当int2x存在时,@圣地亚哥亚历山德里方法运作良好.

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比范围窄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+(b-a)/2当它们具有相同的符号时，您也可以使用。请注意，这会给 带来偏见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，因此编译器可以使用位旋转技术。