编译 | 马超 责编 | 苏宓
出品 | CSDN（ID：CSDNnews）
近日 ， 微软神级人物Raymond Chen在个人博客上 ， 发布了一篇关于《如何计算平均值》的博文 。 这个话题虽然看似平淡无奇 ， 却意外引爆技术圈 ， 并带来无数讨论 。

文章图片

看完这篇博客之后 ， 也让我感叹于国外技术讨论氛围的浓烈 ， 虽然这一话题切入点非常简单 ， 但是最终能够升华至编程之道层面的举轻若重的文章 ， 接下来 ， 我们不妨一起来看看 。
有关求平均数算法的最初版本
有关如何求平均数这个问题 ， Raymond Chen并没有从一开始就炫技 ， 而是循序渐进先放了一段最普通的实现 ， 如下：
unsignedaverage( unsigneda, unsignedb)
{
return(a + b) / 2;
}

CPU	溢出值转为long	变量保留值说明
x86		indefinite integer value
x86		indefinite integer value
ARM	范围0x7FFFFFFFFFFFFFFF	变量赋值最大的正数
ARM		变量赋值最大的正数

因此这段代码在ARM平台上运行时 ， 如果出现溢出情况也并不会返回0 ， 而会是该类型表示最大整数的一半 ， 当然这个最大整数根据处理器的字长不同可能会有所变化 。
return(a + b) / 2
低调的改进版本
接下来Raymond又给出了几种考虑溢出处理 ， 同时又兼顾空间复杂度的方案：
1、变形法：
也就是将（a+b)/2变形 ， 首先找到a和b当中较大的值 ， 设为high ， 较小的值设为low ， 然后把（a+b)/2变成high-(high-low)/2或者low+(high-low)/2 ， 如下：
unsignedaverage( unsignedlow, unsignedhigh) {
returnlow + (high - low) / 2;
}
这种方法所需要的运算量是先进行一次比较以确定两个输入的大小 ， 然后还需要再做两次加法（在计算机运算中加法和减法其实是基本等效的）和一次除法 ， 最终得到答案 。
2、除法前置方案：
也就是先对两个输入进行除2操作 ， 即把（a+b)/2转换为a/2+b/2 ， 当然这种方法需要考虑个位丢失的问题 ， 比如说1/2在整形运算当中的结果会是0 ， 因此1/2+1/2的结果是0而不是1 ， 此时需要把两个输入的个位提取出来进行修正 ， 具体如下：
unsignedaverage( unsigneda, unsignedb) {
return(a / 2) + (b / 2) + (a & b & 1);
}
这个算法当中的计算量是两次除法 ， 两次加法和一次与运算操作 。
3.SWAR法
SWAR法也非常的巧妙 ， 它的本质思路就是把求平均值变成位运算 ， 位操作其实就是二进制的操作 ， 如果我们按位考虑输入值与输出结果的对应关系 ， 那么会有以下的需求要点：

1. 输入都是0 ， 输出结果是0
2. 输入都是1 ， 输出是1
3. 输入是一个0一个1 ， 那么输出结果就是1/2

而满足以上条件的位运算 ， 是与运算加上异常运算除2的结果 ， 即(a and b) + (a xor b )/2 ， 如下：
unsignedaverage( unsigneda, unsignedb) {
return(a & b) + (a ^ b) / 2; // 变体 (a ^ b) + (a & b) * 2
}
至于(a and b) + (a xor b )/2这个等式为什么能满足求平均值的要求 ， 大家根据各种输入的情况都列一下就一目了然了 。 在这种方案下的计算量是两次位运算、一次加法运算以及一次除法运算来完成 。
空间换时间的改进版本
在算法设计当中有一个最基本的常识 ， 空间复杂度与时间复杂度是对跷跷板 ， 上一节的储多算法当中 ， 基本都是牺牲时间复杂度为代价来换取对于溢出的正确处理 ， 那么反过来讲也完全可以用空间换时间 ， 比如现在我们大多数的终端电脑都是64位机了 ， 没必要为了32位长的整形溢出问题而烦恼 ， 直接把类型转换为Long再计算结果就可以了 。