计算两个数的平均数

发表于 更新于 阅读次数：

计算两个数的平均数，如何不溢出？

如果有两个数相加可能溢出，那么如何计算他们的平均值。对于正数和负数，正溢出和负溢出，计算方式可能不一样。

正数，正溢出

示例：计算 Integer.MAX_VALUE 和 Integer.MAX_VALUE 的平均值。

因为 int 类型的二进制位的第一位是符号位，第一位为0代表整数，第一位为1代表负数。

正数计算如果有可能溢出的时候，会向符号为进位，导致符号变为1。此时我们可以把符号位当作普通位来使用，相当于把 int 型看作了 unsigned int 型。在 Java 中，移位运算符 >> 不移动符号位。但是在这种情况中因为我们把符号为看作普通位了，所以需要移动符号位，可以使用 >>> 移位运算符。

代码：

1
2
3
int a = Integer.MAX_VALUE;
int b = Integer.MAX_VALUE;
int average = (a + b) >>> 1;

对于 Long.MAX_VALUE 可以采用同样的方法。

C++ 中没有 >>> 运算符，可以写成：

1
average = ((unsigned int)a + (unsigned int)b)) >> 1;

参考：Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken - Joshua Bloch

负数，负溢出

示例：计算 Integer.MIN_VALUE 和 Integer.MIN_VALUE 的平均值。

从正数溢出的情况应该可以看出来，溢出实际上就是符号位的溢出，其他位其实是正常的。对于负数同样如此。

负数溢出的时候，符号位会变成0，也就是从负数变成了正数。移位运算之后可以保证除了符号位之外的其他位是符合要求的，还需要把符号位从0变为1。

如果想要让符号为变为为 1，那么可以和最高位是1，其他位都是0的常数做与运算。最高位是1，其他位都是0的数，其十六进制形式为 0x80000000，所以代码可以写成：

1
2
3
int a = Integer.MIN_VALUE;
int b = Integer.MIN_VALUE;
int average = ((a + b) >> 1) | 0x80000000;

完整测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class AverageTest {
    public static void main(String[] args) {
        int a = Integer.MAX_VALUE;
        int b = Integer.MAX_VALUE;
        int positiveAverage = (a + b) >>> 1;
        System.out.printf("Value of Integer.MAX_VALUE:      %d\n", Integer.MAX_VALUE);
        System.out.printf("Average of two Integer.MAX_VALUE:%d\n", positiveAverage);

        System.out.println("\n--------------------------------------------\n");

        int c = Integer.MIN_VALUE;
        int d = Integer.MIN_VALUE;
        int negativeAverage = ((c + d) >> 1) | 0x80000000;
        System.out.printf("Value of Integer.MIN_VALUE:      %d\n", Integer.MIN_VALUE);
        System.out.printf("Average of two Integer.MIN_VALUE:%d\n", negativeAverage);
    }
}

参考资料

  1. Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken - Joshua Bloch