找到两个值的平均值的正确方法是什么？

Question

我最近了解到整数溢出是C中未定义的行为(侧面问题 - 它是否也是C++中的UB？)

经常在C语言编程,你需要找到两个值的平均值a和b.但是,这样做(a+b)/2会导致溢出和未定义的行为.

所以我的问题是-什么是找到两个值的平均值的正确方法a,并b用C？

Answer 1

在Secure Coding的帮助下

if (((si_b > 0) && (si_a > (INT_MAX - si_b))) ||
    ((si_b < 0) && (si_a < (INT_MIN - si_b))))
{
  /* will overflow, so use difference method */
  return si_b + (si_a - si_b) / 2;
} 
else
{
 /* the addition will not overflow */
  return (si_a + si_b) / 2;
}

附录

感谢@chux指出舍入问题.这是一个经过正确舍入测试的版本......

int avgnoov (int si_a, int si_b)
{
    if ((si_b > 0) && (si_a > (INT_MAX - si_b)))
    {
      /* will overflow, so use difference method */
      /* both si_a and si_b > 0; 
          we want difference also > 0
          so rounding works correctly */
      if (si_a >= si_b)
        return si_b + (si_a - si_b) / 2;
      else
        return si_a + (si_b - si_a) / 2;
    } 
    else if ((si_b < 0) && (si_a < (INT_MIN - si_b)))
    {
      /* will overflow, so use difference method */
      /* both si_a and si_b < 0; 
          we want difference also < 0
          so rounding works correctly */
      if (si_a <= si_b)
        return si_b + (si_a - si_b) / 2;
      else
        return si_a + (si_b - si_a) / 2;
    }
    else
    {
     /* the addition will not overflow */
      return (si_a + si_b) / 2;
    }
}

Answer 2

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

c int数学中的shift语句(x >> i)等于2除以i的幂.所以声明(a >> 1)+(b >> 1)与a/2 + b/2相同.但是,也需要添加数字截断部分的平均值.该值可以通过掩蔽(a&1),添加((a&1)+(b&1))和除(((a&1)+(b&1))>> 1)来获得.平均值变为(a >> 1)+(b >> 1)+(((a&1)+(b&1))>> 1)

注意:使用>>和&而不是/和%作为除法和余数运算符的原因之一是效率.

Answer 3

一个简单的方法如下

int c = a / 2 + ( b + a % 2 ) / 2;

例如a和b可以表示为

a = 2 * n + r1;
b = 2 * m + r2;

然后

( a + b ) / 2 => ( 2 * n + r1 + 2 * m + r2 ) / 2 => 2 * n / 2 + ( b + r1 ) / 2

最后一个表达式给你

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

更正确的表达方式如下

int c = a / 2 + b / 2 + ( a % 2 + b % 2 ) / 2;

例如，如果我们有

int a = INT_MAX;
int b = INT_MAX;

然后 c 计算为

int c = a / 2 + b / 2 + ( a % 2 + b % 2 ) / 2;

会给c == INT_MAX

编辑：计算机运算符的效果和数学运算符的效果之间发现了有趣的差异。例如根据数学-1可以表示为

-1 = -1 * 2 + 1 

即根据公式

a = 2 * n + r1

2 * n应为小于或等于 tp 的整数a

所以小于-1的数是-2。:)

我认为我所展示的一般公式是可行的，要求对于奇数负数，将考虑小于奇数负数的偶数负数。

看来正确的公式如下

int c = ( a < 0 ? a & ~1 : a ) / 2 + 
        ( b < 0 ? b & ~1 : b ) / 2 + 
        ( ( a & 1 ) + ( b & 1 ) ) / 2;

需要注意的是，从数学角度来看，-1和的平均值-2应等于-2，并且该公式给出了正确的结果。:)