稳妥且高效的两数平均值算法

什么?求两个整数的平均值还能玩出啥花样啊！不就是两个之和然后除以2嘛。是的，没错。在数学教科书中，求两个整数的平均值，就是求两数之和然后除以2那么简单，但是在计算机领域，还真能玩出很多花样来。在编程过程中，追求正确和速度是永恒的主题，这就催生了很多奇妙且高效的算法。

首先分析一下，一般的求平均值公式：

图1 两数平均值公式

此公式很简单，只需要一个加指令和一个除法指令就可以了。但是在计算机中，这个公式有两个问题：

1、x+y 的结果有可能超出了整型数的表达范围，从而造成溢出，最终结果是错误的。

2、除法指令耗时是加法和位操作指令的几十倍到几百倍之多，除法指令的效率很低。

那么，有没有什么方法，可以避免以上两个问题呢？有的，下面介绍一种稳妥并高效的求平均值算法。

如果，x和y，都是有符号的整型数，那么二者的平均值可以利用以下方法计算如下：

图2 高效的均值计算方法

上式中，&表示位与，>>表示右移，圆圈中的加号，表示异或。求出平均值，一共需要7个基本的指令。上式编写成C程序如下：

int t=(x&y)+((x^y)>>1);int avg=t+((t>>31)&(x^y));

有些特例，可以用更快的办法算出来，比如假设x和y都是带符号的非负数，那么只需要使用以下代码，就可以计算出平均值：

图3 更快的平均值算法

结束语：

大家好！我是一个致力于高性能计算的算法工程师，很高兴在头条与大家分享一些有用的计算技巧，以后我会经常发布一些与计算有关的干货，如果大家觉得有用，请多多关注！

以上内容由优质教程资源合作伙伴 “鲸鱼办公” 整理编辑，如果对您有帮助欢迎转发分享！

你可能对这些文章感兴趣：

• Excel表格十大函数(Excel表格函数公式出现错误怎么办?)
• 对不起！忘了告诉你如何激活win10LTSC版，比windows7流畅干净
• Mac新手使用技巧——Mac音量调节
• 新入手的iPhone 13，记得提前打开这5个功能，让手机更好用
• iPhone状态栏中怎么显示图标 状态栏爱心等图标设置方法
• iphone应用图标大小要怎么调整？(iPhone应用图标大小)
• 有办法了！批量删除多个Word页眉页脚
• Excel常用函数知识：使用RANK.EQ或RANK.AVG函数进行排名计算
• RANKIF？Excel中有这个函数吗？
• 手机与和U盘的连接及文件操作(手机直接连接u盘为什么不能互传文件)