计算两个数的平均数,如何不溢出?
如果有两个数相加可能溢出,那么如何计算他们的平均值。对于正数和负数,正溢出和负溢出,计算方式可能不一样。
正数,正溢出
示例:计算 Integer.MAX_VALUE
和 Integer.MAX_VALUE
的平均值。
因为 int 类型的二进制位的第一位是符号位,第一位为0代表整数,第一位为1代表负数。
正数计算如果有可能溢出的时候,会向符号为进位,导致符号变为1。此时我们可以把符号位当作普通位来使用,相当于把 int 型看作了 unsigned int 型。在 Java 中,移位运算符 >>
不移动符号位。但是在这种情况中因为我们把符号为看作普通位了,所以需要移动符号位,可以使用 >>>
移位运算符。
代码:
1 | int a = Integer.MAX_VALUE; |
对于 Long.MAX_VALUE
可以采用同样的方法。
C++ 中没有 >>>
运算符,可以写成:
1 | average = ((unsigned int)a + (unsigned int)b)) >> 1; |
负数,负溢出
示例:计算 Integer.MIN_VALUE
和 Integer.MIN_VALUE
的平均值。
从正数溢出的情况应该可以看出来,溢出实际上就是符号位的溢出,其他位其实是正常的。对于负数同样如此。
负数溢出的时候,符号位会变成0,也就是从负数变成了正数。移位运算之后可以保证除了符号位之外的其他位是符合要求的,还需要把符号位从0变为1。
如果想要让符号为变为为 1,那么可以和最高位是1,其他位都是0的常数做与运算。最高位是1,其他位都是0的数,其十六进制形式为 0x80000000
,所以代码可以写成:
1 | int a = Integer.MIN_VALUE; |
完整测试代码
1 | public class AverageTest { |