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

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

通常在C编程中，您需要找到两个值a和b的平均值。 但是，执行(a+b)/2会导致溢出和未定义的行为。

所以我的问题是 – 在C中找到两个值a和b的平均值的正确方法是什么？

Answer 1

在安全编码的帮助下

 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的整数

所以-1的数字是-2。 🙂

我认为我所显示的通用公式是可行的，对于奇数负数，要求甚至可以考虑小于奇数负数的负数。

似乎正确的公式看起来像

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

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

Answer 4

如果您担心溢出，可以将值转换为更大的类型以执行数学运算，然后执行边界检查。

Answer 5

这是在一个指令周期中计算两个舍入为零的整数的平均值 ：

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

你必须考虑到：

• 它的实现定义了右移一个负整数是否将零或一个移位到高位。 许多CPU通常有两个不同的指令：算术右移（保留符号位）和逻辑右移（不保留符号位）。 允许编译器选择（大多数编译器选择算术移位指令）。

  ISO / IEC 9899：2011§6.5.7按位移位算子

  ¶5E1的结果>> E2是E1右移E2位的位置。 [CUT]如果E1具有带符号类型和负值，则结果值是实现定义的。

  将表达式更改为：

   a / 2 + b / 2 + (a & b & 0x1) 

  不是解决方案，因为逻辑右移相当于仅对正数或无符号数除以2的幂。

• (a & b & 0x1)也没有明确定义。 当a和b都是奇数时，该项应该是非零的。 但它的补码表示失败，ISO C第6.2.6.2/2节规定， 实现可以选择积分数据类型的三种不同表示之一 ：

  • 两个补充
  • 一个补充
  • 符号/幅值

  （通常两者的补充远远超过其他补充）。

Answer 6

在整个范围[INT_MIN...INT_MAX]平均两个int的最简单（通常是最快）的方法是求助于更宽的整数类型。 （建议@ user3100381 。）让我们称之为int2x 。

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

当然，这需要更广泛的类型 – 所以让我们看一个不需要更广泛类型的解决方案。

挑战：

问：当一个int是奇数而另一个是偶数时，应该采用哪种方式进行舍入？
答：遵循上面的average_int()并向0舍入（截断）。

问：代码可以使用%吗？
答：使用前C99代码时， a % 2结果在a < 0时允许不同的结果。 所以我们不要使用% 。

问： int是否需要关于正数和负数的对称范围？
答：由于C99，负数的数量与正数的数量相同（或者更多）。 让我们尽量不要求这个。

解：

执行测试以确定是否可能发生溢出。 如果没有，简单使用(a + b) / 2 。 否则，将差值的一半（与答案相同）添加到较小的值。

以下给出与average_int()相同的答案，而不使用更宽的整数类型。 它可以防止int溢出 ，并且不需要INT_MIN + INT_MAX为0或-1。 它不依赖于编码为2的补码，1的补码或符号幅度。

 int avgC2(int a, int b) { if (a >= 0) { if (b > (INT_MAX - a)) { // (a+b) > INT_MAX if (a >= b) { return (a - b) / 2 + b; } else { return (b - a) / 2 + a; } } } else { if (b < (INT_MIN - a)) { // (a+b) < INT_MIN if (a <= b) { return (a - b) / 2 + b; } else { return (b - a) / 2 + a; } } } return (a + b) / 2; } 

最多3个if() s与任何int对出现。

Answer 7

如果你只需要处理无符号整数类型（并且可以用二进制思考），你可以将你的加法分解成digit并carry 。 我们可以写a+b （无限精度）作为(a^b) + ((a&b)<<1)) ，所以(a+b)/2只是((a^b)>>1) + (a&b) 。 最后一个表达式适合a和b的常见类型，因此您可以在代码中使用它：

 unsigned semisum(unsigned a, unsigned b) { return ((a^b)>>1) + (a&b); } 

Answer 8

最简单的答案如果只有2个元素可以避免溢出：

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

对于更多元素，您可以使用：

 (a/x) + (b/x) + (c/x) + (d/x) ..... = average //x = amount of elements 

从数学的角度来看 ，如果原始值之前没有这样做，这将永远不会达到溢出 ，因为你没有真正地将它们全部加在一起，而是在将它们加在一起之前将它们分开 。 因此，在计算过程中执行的任何操作（包括结果）的结果都不会 比最大的初始元素 （假设您只使用Real Numbers ） 更大 （到0的任一侧）。

所以做以下事情：

1. 确定’C’中的元素数量，让我们称之为total 。
2. 声明一个值来存储平均值，让我们称之为average 。
3. 声明一个值来存储余数，让我们称之为remainder 。
4. 通过它们迭代并：
   • 将当前元素除以总金额。
   • 将结果添加到average 。
   • 将剩余的分割值加在一起， remainder 。
5. 除去余数并将其加到average 。
6. 用您需要/打算的平均值做。

这将给你一个最多1的答案（十进制数字系统[基数10]）。 我还不知道C ++，所以我只能在C＃中给你一个例子。

C＃中的伪代码（只是为了提供一个想法）：

 int[] C = new int[20]; //The array of elements. int total = C.Length; //The total amount of elements. int average = 0; //The variable to contain the result. int remainder = 0; //The variable to contain all the smaller bits. foreach (int element in C) //Iteration { int temp = (element / total); //Divide the current element by the total. average = average + temp; //Add the result to the average. temp = (temp % total); //Get the remainder (number that was not divided) remainder = remainder + temp; //Add remainder to the other remainders. } average = average + (remainder / total); // Adds the divided remainders to the average. 

压缩C＃示例：

 int[] C = new int[20]; //The array of elements. int total = C.Length; //The total amount of elements. int average = 0; //The variable to contain the result. int remainder = 0; //The variable to contain all the smaller bits. foreach (int element in C) //Iteration { average += (element / total); //Add the current element divided by the total to the average. remainder += ( element % total); //Add the remainders together. } average += (remainder / total); //Adds the divided remainders to the total.