| 29 | [Divide Two Integers][029] | Math, Binary Search |

[029]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/029/README.md

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

**Tags:** Math, Binary Search

题意是让你算两个整型数相除后的结果，如果结果溢出就返回 `MAX_INT`，但不能使用乘、除、余的操作符，如果是用加减操作符的话肯定会超时哈，这样的话我们就只能想到位操作符了。

首先，我们分析下溢出的情况，也就是当被除数为 `Integer.MIN_VALUE`，除数为 `-1` 时会溢出，因为 `|Integer.MIN_VALUE| = Integer.MAX_VALUE + 1`。

然后，我们把除数和被除数都转为 `long` 类型的正数去做下一步操作，我这里以 `22` 和 `3` 相除为例子，因为 `22 >= 3`，我们对 `3` 进行左移一位，也就是乘 2，结果为 `6`，比 `22` 小，我们继续对 `6` 左移一位结果为 `12`，还是比 `22` 小，我们继续对 `12` 左移一位为 `24`，比 `22` 大，这时我们可以分析出，`22` 肯定比 `3` 的 `4` 倍要大，`4` 是怎么来的？因为我们左移了两次，也就是 `1 << 2 = 4`，此时我们记下这个 `4`，然后让 `22 - 3 * 4 = 10`，因为 `10 >= 3`，对 `10` 和 `3` 进行同样的操作，我们可以得到 `2`，此时加上上次的 `4`，和为 `6`，也就是 `22` 比 `3` 的 `6` 倍要大，此时还剩余 `10 - 6 = 4`，因为 `4 >= 3`，所以对 `4` 和 `3` 进行同样的操作，我们发现并不能对 `3` 进行左移了，因为 `4 >= 3`，所以 `1` 倍还是有的，所以加上最后的 `1`，结果为 `6 + 1 = 7`，也就是 `22` 整除 `3` 结果为 `7`，根据以上思路来书写如下代码应该不是难事了吧。

class Solution {

public int divide(int dividend, int divisor) {

if (dividend == Integer.MIN_VALUE && divisor == -1) {

return Integer.MAX_VALUE;

}

long dvd = Math.abs((long) dividend);

long dvr = Math.abs((long) divisor);

int res = 0;

while (dvd >= dvr) {

long temp = dvr, multiple = 1;

while (dvd >= temp << 1) {

temp <<= 1;

multiple <<= 1;

}

dvd -= temp;

res += multiple;

}

return (dividend < 0) ^ (divisor < 0) ? -res : res;

}

}

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-java-leetcode][ajl]

[title]: https://leetcode.com/problems/divide-two-integers

[ajl]: https://github.com/Blankj/awesome-java-leetcode

package com.blankj.medium._029;

public class Solution {

public int divide(int dividend, int divisor) {

if (dividend == Integer.MIN_VALUE && divisor == -1) {

return Integer.MAX_VALUE;

}

long dvd = Math.abs((long) dividend);

long dvr = Math.abs((long) divisor);

int res = 0;

while (dvd >= dvr) {

long temp = dvr, multiple = 1;

while (dvd >= temp << 1) {

temp <<= 1;

multiple <<= 1;

}

dvd -= temp;

res += multiple;

}

return (dividend < 0) ^ (divisor < 0) ? -res : res;

}

public static void main(String[] args) {

Solution solution = new Solution();

System.out.println(solution.divide(-2147483648, 1));

}

}