求两整数平均值

今天来讲点基础的东西，求两整数的平均值，你可能笑了，这谁不会，放在小学生眼里都是几秒钟就能解决的事。

那么我再加个约束条件，用代码写一个求两整数平均值的算法，你可能又笑了，这不是一样么，来，给你写一个：

public static int mean(int a, int b) {
    return (a + b) / 2;
}

你想更高效或者更省内存？再来两个。

无符号右移：

public static int mean(int a, int b) {
    return (a + b) >>> 1;
}

有符号右移：

public static int mean(int a, int b) {
    return (a + b) >> 1;
}

这种方法可以直接操控二进制，右移操作实际上就是挤掉最右边的位，并在最左边的空位补数，无符号右移补 0，有符号右移则正数补 0，负数补 1，即保持符号不变。

这种方法为何可以实现求平均数呢？

举个例子，比如 2 和 4 的二进制表示分别是 0010 和 0100，和为 6，也就是 0110，右移为 0011，也就是 3，说明这个算法是可行的，原理其实就是二进制中只有 0 和 1，求平均时就是将该位除以 2，如果该位为 1，自然就变成了 0，并分给后一位 1，所以从视觉上来看就是右移操作。

你可能会想到了，如果出现了奇数呢？假如 2 和 3 取平均值，相加得 5，也就是 0101，右移后结果为 0010，有点奇怪是吧，但是不要忘了，在程序中整数执行 / 运算，得到的也是整数，程序会自动截断小数点后的内容，也不进行四舍五入，得出结果是 2，无误。

这就是最好的算法了吗？并不是。

相信你学计算机基础的时候，就知道了 int 的范围，如果不加以判断，就会产生溢出，比如两个数 0xffff 和 0001 相加，就会产生结果溢出，平均值计算结果为 0，明显是错误的。

那么我们就需要一种安全的防溢出的计算方法：

public static int mean(int a, int b) {
    return (x & y) + ((x ^ y) >> 1);
}

简单的解释就是：

• 将相同的位进行相加，结果等于两数按位与的结果的两倍。
• 将不同的位进行相加，其结果等于按位异或的结果。

相信你也是一脸懵逼的，& 和 ^ 都是位运算，任何数据中只有三种情况：

• 0 和 0 对应，对应位都为 0，相加后再除以 2 还是 0，不需要计算。
• 0 和 1 对应，对应位有且仅有一位是 1，用异或运算 ^ 提取出来，然后 >> 右移一位，相当于除以 2。
• 1 和 1 对应，对应位都为 1，相加后再除以 2 还是原来的数，也就是按位与运算 &。

最后将这三种情况汇总即可得出结果，而且不会产生高位溢出。