时间戳

首页 > 解决方案 > 寻找以下溢出规避技巧的理论

java - 寻找以下溢出规避技巧的理论

问题描述

以下代码使用了一些我试图理解的整数溢出预防技巧：

// x,y,z are positive numbers
boolean check(long x, long y, long z) {
  return x >= (z+y-1)/y;
}

根据问题定义，我假设代码的实际意图是：

return x*y >= z;

看起来作者通过以下思路避免了整数溢出：

1. x*y >= z
2. x >= z / y //Divide both sides by y
3. x - 1 >= (z - 1) / y //Subtract 1 from left side and dividend
4. x >= (z - 1) / y + 1 //Move 1 to the right side
5. x >= (z + y - 1) / y //Place 1 inside the brackets

第3点是我想要理解的。

第二个不等式与最初的意图不同（例如 x=10, y=10, z=101），但第三点可以作为一种解决方法（基于我的测试）。

你能解释一下这背后的理论吗？

标签： javainteger-overflowinteger-divisioninequality

解决方案

问题是涉及整数除法。

  • x*y >= z
  • x >= z / ((双)y)

或者积分溢出将是

  • x >= ceil(z / ((双)y))

哪个是整数除法（截断余数）

  • x >= (z + y - 1) / y

或以不同的方式表述：given z = m*y + n, where 0 <= n < y，则对于 n == 0，上述除法将给出m，否则m+1为上限。下面没有可能的溢出x。

推荐阅读