![[LeetCode] 29. Divide Two Integers ☆☆ [LeetCode] 29. Divide Two Integers ☆☆](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
解法:
这道题让我们求两数相除,而且规定我们不能用乘法,除法和取余操作。
采用位运算中的移位运算,左移一位相当于乘2,右移一位相当于除以2。假设求 a / b,将b左移n位后大于a,则结果 res += 1 << (n - 1),将a更新 (a -= b << (n - 1)) 后进行同样操作,直到 a < b。
public class Solution {
public int divide(int dividend, int divisor) {
if (divisor == 0) {
return Integer.MAX_VALUE;
} if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
} boolean isNeg = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0); long left = Math.abs((long)dividend);
long right = Math.abs((long)divisor);
int result = 0;
while (left >= right) {
int times = 1;
while ((right << times) <= left) {
times++;
}
left -= (right << (times - 1));
result += (1 << (times - 1));
} return isNeg ? -result : result;
}
}