曲径通幽论坛

标题: 使用 (x&y) + ((x^y)>>1) 求平均数 [打印本页]

作者: beyes 时间: 2011-11-15 23:20
标题: 使用 (x&y) + ((x^y)>>1) 求平均数
在一个面试题里见到这么一道题：

下面的代码：

[Plain Text] 纯文本查看 复制代码

int func (int x, int y)

{

   return (x&y) + ((x^y)>>1);

}

当 x 为 729，y 为 271 时函数的返回值是多少？

思路最简单也最直接的就是将 x 和 y 都先转换为二进制，然后老老实实的做按位与，按位异或等运算，最后得出结果。

在分析该表达式的实现思路之前，首先说明该表达式的作用就是求两数的平均值。也就是说，像上面当 x 为 729，y 为 271 时函数的返回值是 500 。下面说明该表达式的思路。

我们先了解下面几种情况：

1. 当两个数所有为 1 和为 0 的位都相同时，这两个数的平均值就是 (x & y) 。比如当 x 和 y 都等于 1100 时，x & y 的值也是 1100 ，我们也可以说此时求 x 和 y 的平均数可以用 (x & y) 来求得。

2. 当两个数中的所有对应位有且只有一个为 1 时，那么这两个数的平均值由 (x^y)>>1 表达式求得。比如当 x 为 101100 (十进制 44)，y 为 010010 (十进制 18) 时，x ^ y 的值为 111110 ，然后再将 111110 向右移动 1 位后得 11111 (十进制为 31)，也就是 (44 + 18)/2 = 31 。

由上面的情况1 和情况2 我们知道，将它们两者结合起来便可求得随意两个整数的平均值。下面以 x 等于 12， y 等于 24 为例说明：

x 的二进制数位 1100 ，y 的二进制数为 11000 。我们先将 x 和 y 做相与运算：

01100
11000 &
--------------
01000

实际上，像上面的运算，我们也可以直接看成是情况1 中的运算，即相当于执行：01000 & 01000 ，最后值仍然是 01000 。

好，经过上面的与运算后，看起来是将 01100 和 11000 分别去掉了 01000 这部分，所以剩下来的就是 00100 和 10000 。当我们执行 x^y 时：

01100
11000 ^
-----------
10100

由上可见，异或的运算正好也是去掉了 01000 ，然后将剩下来的 00100 和 10000 这两部分进行相加，所以求这两部分的平均数只要向右移动 1 位即可。

综上可得，我们求平均数的过程是先用与运算对数值做部分的提取，然后用异或并右移运算获得余下部分的平均值，因此这两部分的平均值相加后就得出了原来两数的平均值。实际上，这是一个加法分解然后综合的过程。如上面的 12 和 24，先做与运算，也就相当于从 12 和 24 里分别先减去 4，剩下 8 和 16，再将这两数相加得 24 (异或运算)，然后再除以2(右移)，结果为 12 。最后 12 + 4 等于 16 即得最后所要的结果。

尽管上面的过程看来上去实际用处不是很大，但如果是用在没有乘除法指令的简单单片机系统，移位和逻辑运算操作就显得很重要了。

欢迎光临曲径通幽论坛 (http://www.groad.net/bbs/)