南京外贸网站建站,wordpress $post->id,企业网站制作深圳,家装品牌排行榜前十名【Java】再一次踩了整数溢出的坑 一、起因原题示例 1示例 2提示 我的代码提交结果 二、思考修改后的代码如下 三、知识点1. int m l ((r - l) / 2)解释 2. if (m x / m)解释 四、结尾 一、起因
我在做【力扣】69.x 的平方根 一题的时候#xff0c;明明觉得逻辑没问题int m l ((r - l) / 2)解释 2. if (m x / m)解释 四、结尾 一、起因
我在做【力扣】69.x 的平方根 一题的时候明明觉得逻辑没问题可答案就是不对。
原题
给你一个非负整数 x 计算并返回 x 的算术平方根。 由于返回类型是整数结果只保留整数部分小数部分将被舍去。 注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1 输入x 4 输出2 示例 2 输入x 8 输出2 解释8 的算术平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。 提示
0 x 231 - 1
我的代码
class Solution {public int mySqrt(int x) {//处理特殊值 0 和 1if (x 0) {return 0;}if (x 1) {return 1;}//二分法查找int l 1, r x / 2;while (l r) {int m l ((r - l) / 2);if (m * m x) {return m;} else if (m * m x) {l m 1;} else {r m - 1;}}if (r l) {return r;} else {return l;}}
}提交结果 输入2147395599 输出1073697799 预期结果46339 二、思考
我反复检查代码的逻辑都没发现问题出现在哪里直到我看见 别人的题解。 对比代码之后我恍然大悟明白自己又踩了整数溢出的坑。
修改后的代码如下
class Solution {public int mySqrt(int x) {//处理特殊值 0 和 1if (x 0) {return 0;}if (x 1) {return 1;}//二分法查找int l 1, r x / 2;while (l r) {int m l ((r - l) / 2);if (m x / m) {return m;} else if (m x / m) {l m 1;} else {r m - 1;}}return r;}
}三、知识点
1. int m l ((r - l) / 2)
写 int m l ((r - l) / 2) 而不是直接写 int m (l r) / 2 是为了防止整数溢出。
解释 假设我们写的是 int m (l r) / 2 当 l 和 r 都是非常大的正整数时接近 Integer.MAX_VALUE即 2147483647l r 可能会超过 int 类型的最大表示范围 (2^31 - 1)这会导致溢出结果会变成负数从而导致程序的行为不符合预期。 如 l 2000000000r 2000000000那么 l r 4000000000这是超过 int 的最大值 2147483647 的会产生溢出。 假设我们写的是 int m (l r) / 2 当 r l 时r - l 不会溢出它是一个较小的数(r - l) / 2 也不会产生太大的值最终加上 l依然保持在 int 范围内。
2. if (m x / m)
写 m x / m 而不写 m * m x 也是为了防止整数溢出。
解释
原理同上。 当 m * m 2147483647 时会发生整数溢出结果会变成负数导致程序的行为不符合预期。
四、结尾
当然也可以将 m * m x 改成 (long) m * m x这样就不用担心整数溢出了因为 long 类型的最大值比 int 类型的最大值大得多。
