【029-Divide Two Integers（两个整数相除）】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题
Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT.
题目大意
不使用除法，乘法和取余，求两个整数的相除的结果，如果有溢出就返回最大的整数。
解题思路
任何一个整数可以表示成以2的幂为底的一组基的线性组合，即num=a_0*2^0+a_1*2^1+a_2*2^2+…+a_n*2^n。基于以上这个公式以及左移一位相当于乘以2，我们先让除数左移直到大于被除数之前得到一个最大的基。然后接下来我们每次尝试减去这个基，如果可以则结果增加加2^k,然后基继续右移迭代，直到基为0为止。因为这个方法的迭代次数是按2的幂知道超过结果，，所以时间复杂度为O(log(n))。
代码实现
算法实现类
public class Solution {(int dividend, int divisor) {// 相除时溢出处理if (divisor == 0 || dividend == Integer.MIN_VALUE && divisor == -1) {return Integer.MAX_VALUE;}// 求符号位int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;// 求绝对值，为防止溢出使用longlong dvd = Math.abs((long) dividend);long dvs = Math.abs((long) divisor);// 记录结果int result = 0;// 被除数大于除数while (dvd >= dvs) {// 记录除数long tmp = dvs;// 记录商的大小long mul = 1;while (dvd >= (tmp << 1)) {tmp <<= 1;mul <<= 1;}// 减去最接近dvd的dvs的指数倍的值（值为tmp）dvd -= tmp;// 修正结果result += mul;}return result * sign;}}评测结果
点击图片，鼠标不释放，拖动一段位置，释放后在新的窗口中查看完整图片。
特别说明欢迎转载，转载请注明出处【】
坚硬的城市里没有柔软的爱情，生活不是林黛玉，
