C++ 书上说 (x&y)+((x^y)>>1)的功能是取两个数的平均值,哪位大侠可以帮我解释下啊?

如题所述

很牛X的一个思路,虽然不算高效,但如果在汇编中的话,这种方法可以不产生高位溢出。
我琢磨了一下,大概思路应该是这样:

(x&y)+((x^y)>>1),把x和y里对应的每一位(指二进制位)都分成三类,每一类分别计算平均值,最后汇总。其中,一类是x,y对应位都是1,用x&y计算其平均值;一类是x,y中对应位有且只有一位是1,用(x^y)>>1计算其平均值;还有一另是x,y中对应位均为0,无须计算。

下面我再分别说明一下前两种情况是怎样计算的:

x,y对应位均为1,相加后再除以2还是原来的数,如两个00001111相加后除以2仍得00001111,这是第一部分。
第二部分,对应位有且只有一位为1,用“异或”运算提取出来,然后>>1(右移一位,相当于除以2),即到到第二部分的平均值。
第三部分,对应位均为零,因为相加后再除以二还是0,所以不用计算。
三部分汇总之后就是(x&y)+((x^y)>>1)

顺便解释一下前面说到可以避免溢出。
假设x,y均为unsigned char型数据(0~255,占用一字节),显然,x,y的平均数也在0~255之间,但如果直接x+y可能会使结果大于255,这就产生溢出,虽然最终结果在255之内,但过程中需要额外处理溢出的那一位,在汇编中就需要考虑这种高位溢出的情况,如果(x&y)+((x^y)>>1)计算则不会。
温馨提示:内容为网友见解,仅供参考
第1个回答  2018-04-18

(x&y)+((x^y)>>1),把x和y里对应的每一位(指二进制位)都分成三类,每一类分别计算平均值,最后汇总。其中,一类是x,y对应位都是1,用x&y计算其平均值;一类是x,y中对应位有且只有一位是1,用(x^y)>>1计算其平均值;还有一另是x,y中对应位均为0,无须计算。

下面我再分别说明一下前两种情况是怎样计算的:
1)、x,y对应位均为1,相加后再除以2还是原来的数,如两个00001111相加后除以2仍得00001111,这是第一部分。
第二部分,对应位有且只有一位为1,用“异或”运算提取出来,然后>>1(右移一位,相当于除以2),即到到第二部分的平均值。
第三部分,对应位均为零,因为相加后再除以二还是0,所以不用计算。
三部分汇总之后就是(x&y)+((x^y)>>1)

本回答被网友采纳
第2个回答  2011-08-24
相当于|x+y|+|x-y|/2,
第3个回答  2011-08-24
太巧妙了。
相似回答