位运算求平均数

Question

图片描述

[1]: /img/bVm843

解析好像讲的不太清楚，没看懂。高手们详细介绍一下可以么？

Answer 1

1. 右移一位就是 floor(n/2)

所以有 (x+y) shr 1 = floor((x+y)/2)
但这样可能溢出。

逻辑异或就是不进位加：
0^0 = 0
1^0 = 1
1^1 = 0
而逻辑与可以找出进位，所以有：
x+y = (x&y) shl 1 + (x^y)
两边右移一位：
(x+y) shr 1 = ((x&y) shl 1 + (x^y)) shr 1
因为 (x&y) shl 1 是左移来的最后一位肯定是 0, 相加后这一位不会进位，所以右移一位可以分配进去：
(x+y) shr 1 = (x&y) + (x^y) shr 1
这样，由于 (x^y) shr 1 是右移来的，最高位是 0, 所以不会溢出。

Answer 2

对于求x和y的平均值
最常见方法；

（x+y）》1
   这种方法有一个弊端：x、y均为int，那极有可能（x+y）超过int的范围.

接下来就是用操作符求平均数：
（x&y）+（x^y）》1
1: x&y代表逻辑与，当两个数中0和1的位都相同时，两数平均值为x&y。比如x和y都为1011（十进制为11）此时x&y等于1011。
2: x^y代表逻辑异或，当两个数中的所有对应位中有且仅有一个1，两个数的平均值就可以用（x^y）》1获得。比如x为1101（十进制为13），y为0010（十进制为2），x^y的值为1111，右移一位变为0111（十进制为7）

---

从1，2可得任意两个数都可以这样求平均数，因为数字的二进制无非是两种情况，要么相等，要么不等。
return x&y+（x^y）》1；

  手机回答的，可能排版丑爆

```