目的
- 判断两个同类型的值相加是否溢出。
- 判断两个同类型的值相乘是否溢出。
前提
- 阅读这篇文章：https://blog.csdn.net/cqh123hh/article/details/126166549
推导 1
有 x + y = z，若不溢出，输出 z；若溢出，输出 r。
w = 8，当 0 ≦ x,y ≦ 127 时，0 ≦ x + y ≦ 254，即 z ∈ [0, 254]。
当 z ∈ [128, 254] 时，溢出，输出 r 为 z - 256。
例：127 + 3 = 130，输出 130 - 256 = -126。
byte b = 127; b += 3; System.out.println(b);// -126
猜想，是否能用 r - y != x，判断两数相加溢出？
public static boolean isOK_Add(int x, int y) {
int r = x + y;
return r - y == x;
}
目标：
- 如果 z 溢出，证明 r - y != x，即证明此方法返回 false。
没有溢出时，r = z。要求：此方法返回 true。
- x + y = r。
- r - y = x 为 true，此方法返回 true。
由于以 8 位为例，使用 byte 验证。但 Java 中 byte 参与运算时会自动提升为 int 类型，int 类型的取值范围太大，不好验证，所以需要强转。
byte x = 24; byte y = 55; byte r = (byte)(x + y);// 79 // 79 - 55 == 24 System.out.println(r - y == x);// true
溢出时 r = z - 256。要求：此方法返回 false。
- x + y = r + 256。
- r - y = x - 256。
- x ∈ [0, 127]，x - 256 ∈ [-256, -129]。
x - 256 负溢出，r - y 的输出结果为 (x - 256) + 256 = x。此方法返回 true。
推导失败！猜想错误！
byte x = 124; byte y = 55; // 179 正溢出，结果为 179 - 256 = -77 byte r = (byte)(x + y);// -77 // -77 - 55 = -132，负溢出，结果为 -132 + 256 = 124 System.out.println((byte)(r - y) == x);// true
推导 2
0 ≦ x,y ≦ 127 时，z ∈ [0, 254]。
-
当 z ∈ [128, 254] 时，溢出，输出 r 为 z - 256。
-
此时 r ∈ [-128, -2]，为负数，小于 x 且小于 y。
-
所以，如果 r < x，则正溢出。
int r = x + y;
if (x >= 0 && y >= 0) {
return r >= x;
}
-128 ≦ x,y ≦ -1 时，z ∈ [-256, -2]。
- 当 z ∈ [-256, -129] 时，溢出，输出 r 为 z + 256。
- 此时 r ∈ [0, 127]，为非负数，大于 x 且大于 y。
- 所以，如果 r > x，则负溢出。
if (x < 0 && y < 0) {
return r <= x;
}
-128 ≦ x ≦ -1，0 ≦ y ≦ 127 时，z ∈ [-128, 126]，没有溢出，返回 true。
// 返回 true：没有溢出
// 返回 false：溢出
public static boolean isOK_Add(int x, int y) {
int r = x + y;
if (x >= 0 && y >= 0) {
return r >= x;
}
if (x < 0 && y < 0) {
return r <= x;
}
return true;
}
推导 3
有 x * y = z，若不溢出，输出 z；若溢出，输出 r。
两非负数相乘
w = 8，当 0 ≦ x,y ≦ 127 时，0 ≦ x * y ≦ 16129，即 z ∈ [0, 16129]。
当 z ∈ [128, 16129] 时，正溢出。
- 若 z % 256 ∈ [0, 127]，则 r = z % 256。
- 若 z % 256 ∈ [128, 255]，则 r = z % 256 - 256。
猜想，是否能用 r / y != x，判断两非负数相乘溢出？
前提：y != 0 且 x != 0，这些值要提前处理，避免除零异常。
public static boolean isOK_Multiply(int x, int y) {
if (x == 0 || y == 0
|| x == 1 || y == 1) {
return true;
}
int r = x * y;
return r / y == x;
}
目标：
- 如果 z 溢出，证明 r / y != z / y，即证明此方法返回 false。
没有溢出时，r = z。要求：此方法返回 true。
- x * y = r。
- r / y = x 为 true，此方法返回 true。
溢出时 r = z % 256 或 z % 256 - 256。要求：此方法返回 false。
byte b = 50; b *= 30; // 1500 正溢出，1500 % 256 = 220，输出 220 - 256 = -36 System.out.println(b);// -36
当 z % 256 ∈ [0, 127]，r = z % 256 时：
-
r / y = z % 256 / y
-
比较 z % 256 / y 与 z / y。
-
当 z ∈ [0, 255] 时，两式子相等，方法就会返回 true。
-
当 z ≧ 256，两式子不相等，方法就会返回 false。
现有条件：
-
z 溢出，所以 z > 127。
-
z % 256 ∈ [0, 127]，则有 z = 256 * n + k，n 为非负整数，k ∈ [0, 127]。
当 n = 0 时，z = k，z ∈ [0, 127]。
当 n > 0 时，z ≧ 256。
-
两个条件结合，z ≧ 256，所以方法返回 false。
当 z % 256 ∈ [128, 255]，r = z % 256 - 256 时：
- r / y = (z % 256 - 256) / y
- 比较 (z % 256 - 256) / y 与 z / y。
- 当 z % 256 - 256 = z 即 z % 256 = z + 256 时，两个式子相等。
- 然而 z + 256 ≧ 256，z % 256 ∈ [0, 255]，不可能存在 z 使这两个式子相等，方法返回 false。
两负数相乘
当 -128 ≦ x,y ≦ -1 时，1 ≦ x * y ≦ 16384，即 z ∈ [1, 16384]。
当 z ∈ [128, 16384] 时，溢出。
证明过程同上。
一正一负
当 -128 ≦ x ≦ -1，0 ≦ y ≦ 127 时，z ∈ [-16256, 0]。
当 z ∈ [-16256, -129] 时，负溢出。
-
若 z % 256 = 0，则 r = 0。
-
若 z % 256 ∈ [-128, -1]，则 r = z % 256。
-
若 z % 256 ∈ [-255, -129]，则 r = z % 256 + 256。
溢出时，当 z % 256 = 0，r = 0 时：要求：此方法返回 false。
- r / y = 0。
- 比较 0 与 z/y。
- 当 z = 0 时，两式子相等，此方法返回 true。
- 然而负溢出，z != 0，此方法返回 false。
溢出时，当 z % 256 ∈ [-128, -1]，r = z % 256 时：要求：此方法返回 false。
-
r / y = z % 256 / y
-
比较 z % 256 / y 与 z / y。
-
当 z ∈ [-255, 0] 时，两式子相等，方法就会返回 true。
-
当 z < -256 时，两式子不相等，方法就会返回 false。
现有条件：
-
z 负溢出，z < -128。
-
z % 256 ∈ [-128, -1]，则有 z = 256 * n + k，n 为非正整数，k ∈ [-128, -1]。
当 n = 0 时，z = k，z ∈ [-128, -1]。
当 n < 0 时，z < -256。
-
两个条件结合，z < -256，所以方法返回 false。
溢出时，当 z % 256 ∈ [-255, -129]，r = z % 256 + 256 时：要求：此方法返回 false。
- r / y = (z % 256 + 256) / y。
- 比较 (z % 256 + 256) / y 与 z / y。
- 当 z % 256 + 256 = z 即 z % 256 = z - 256 时，两个式子相等。
- 然而 z - 256 ≦ -256，z % 256 ∈ [-255, 0]，不可能存在 z 使这两个式子相等，方法返回 false。
证毕，此方法有效。
