乐趣区

LeetCode刷题——29. Divide Two Integers(Part 2靠大家)

上篇文章写了以我自己的思路来解决这个问题,但是运行时间过长,看了 leetcode 上的高效写法是使用位运算的解法,当初我自己写这个问题是也想到了可以用位运算快一点,但是因为基础差,对位运算的掌握不牢靠,还是选择使用了减法的思路,在此将 leetcode 上高效解法做一个思路分析,加深下自己对位运算的理解
LeetCode 上高效解法代码
class Solution {

public static int divide(int dividend, int divisor) {
// 首先处理 Integer 的最小值溢出问题(和我思路一样)
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
// 判断结果符号(这个写法比我的号,但是结果的时候用到了乘法,难道符合题意??费解????)
int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
// 取被除数最大值
long dvd = Math.abs((long) dividend);
// 取除数最大值
long dvs = Math.abs((long) divisor);
// 定义结果
int res = 0;
// 循环条件:当被除数大于等于除数时候
while (dvd >= dvs) {
// 为防止溢出, 这里使用 long 类型
long temp = dvs;
long mult = 1;
//<< 移位操作, 向左移动 1 位
// 当 dvd 大于 dvs* 2 的 mult 次方的时候, 即计算 dvd 中最多有 2 的几次方个 dvs
while (dvd >= (temp << 1)) {
temp <<= 1;
mult <<= 1;
}
System.out.printf(“%d 里面有,2 的 %d 次方个 %d\r\n”, dvd, mult, dvs);
// 计算新的 dvd, 和累加 mult
dvd -= temp;
res += mult;
}

return res * sign;
}

}
用例
[100,3]
输出结果
100 里面有,2 的 32 次方个 3
4 里面有,2 的 1 次方个 3
总结
上面的算法将以前的减操作优化称为位移操作,一次可以累加 2 的 n 次方个,减少了循环次数,所以比 Part 1 中算法要快

退出移动版