取C中两个有符号数的平均值
让我们说我们有x和y，两者都是C中的有符号整数，我们如何找到两者之间最准确的平均值？
我更喜欢一种不利用任何机器/编译器/工具链特定工作的解决方案。
我提出的最好的是： (a / 2) + (b / 2) + !!(a % 2) * !!(b %2)是否有更准确的解决方案？ 快点？ 更简单？
如果我们知道一个是否比其他先验大？
谢谢。
d
编者注 ：请注意，当输入值接近C int类型的最大绝对边界时，OP期望答案不受整数溢出的影响。 这在原始问题中没有说明，但在给出答案时很重要。
a/2 + b/2 + (a%2 + b%2)/2
似乎最简单的一个不符合实现特性的假设（它依赖于C99，它指定/的结果为“截断为0”，而它依赖于C90的实现）。
它具有不进行测试（因此没有昂贵的跳转）的优点，并且所有分区/余数都是2，因此编译器可以使用位错误技术。
接受答复后（4年）
我希望函数int average_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; }
有更多测试的解决方案 ，但没有%
当溢出没有发生时，所有下面的解决方案“工作”到(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*(ba))/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); }
如果(a^b)<=0你可以使用(a+b)/2而不用担心溢出。
否则，尝试(a-(a|b)+b)/2+(a|b)/2 。 -(a|b)至少与a和b一样大，并且具有相反的符号，因此这避免了溢出。
我迅速做到了这一点，所以可能会有一些愚蠢的错误。 请注意，这里没有特定于机器的黑客攻击 。 所有行为完全由C标准确定，并且它需要有符号值的二进制补码，一补码或符号幅度表示，并指定逐位运算符在逐位表示中工作。 不， a|b的相对大小取决于表示......
编辑：当他们有相同的符号时，您也可以使用a+(ba)/2 。 请注意，这将偏向a 。 你可以扭转它并对b产生偏见。 另一方面，如果我没有弄错的话，我上面的解决方案会偏向零。
另一种尝试：一种标准方法是(a&b)+(a^b)/2 。 在二进制补码中，无论符号如何，它都可以工作，但我相信如果a和b具有相同的符号，它也可以在补码或符号量级中起作用。 小心检查一下？
只是一些可能有帮助的观察结果：
“最准确”并不一定是整数唯一的。 例如，1和4,2和3是同样“最准确”的答案。 数学上（不是C整数）：
(a+b)/2 = a+(ba)/2 = b+(ab)/2
让我们试着打破这个：
- 如果符号（a）！=符号（b）则a + b将不会溢出。 这种情况可以通过比较二进制补码表示中的最高有效位来确定。
- 如果符号（a）==符号（b），那么如果a大于b，（ab）将不会溢出。 否则（ba）不会溢出。 编辑：实际上两者都不会溢出。
你想要准确地优化什么？ 不同的处理器架构可能有不同的最佳解决方案 例如，在代码中用AND替换乘法可以提高性能。 同样在二进制补码架构中，您可以简单地（a＆b＆1）。
我只是想抛出一些代码，看起来不是太快但也许有人可以使用和改进：
int sgeq = ((a<0)==(b<0)); int avg = ((!sgeq)*(a+b)+sgeq*(ba))/2 + sgeq*a
对于无符号整数，平均值是（x + y）/ 2的最低值。 但是签名整数也是如此。 对于总和为奇数的整数，此公式失败，因为它的最低值比其平均值小1。
您可以在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求解器检查了它的正确性
我会这样做，将两者转换为long long（64位有符号整数）加起来，这不会溢出然后将结果除以2：
((long long)a + (long long)b) / 2
如果您想要小数部分，请将其存储为double。
重要的是要注意结果将适合32位整数。
如果您使用的是最高等级的整数，那么您可以使用：
((double)a + (double)b) / 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用于此测试
首先，双重否定是不必要和多余的。 你可以简化这种方式。
此外， (a+b)/2是完全准确的。 如果你想用包含的一半来表示你的答案，那么在你分裂之前把它们抛到浮子上。
编辑：对于无法用int表示答案的情况……好吧，答案是，你不能用int表示它。 抱歉。 你可以使用long int，但这可能是作弊。