1. 原题链接
2. 题目要求
给出被除数dividend和除数divisor，求出二者相除的商，余数忽略不计。
注意：不能使用乘法、除法和取余运算
3. 解题思路
陷阱一：MIN_VALUE/-1会溢出。因为Integer.MIN_VALUE = -的绝对值比Integer.MAX_VALUE大1
陷阱二：除数divisor不能等于“0”
思路一：使用一个while循环，当dividend >= divisor时，进入循环。dividend = divident - divisor，每减一次计数器res+1。循环结束后则得到二者之商。
缺点：时间复杂度为O( n )，当被除数很大、除数很小时，效率非常低
3 public class DivideTwoIntegers29 { 4 public static void main(String[] args) { 5 System.out.println(divided(-36, -3)); 6 } 7 8 public static int divide(int dividend, int divisor) { 9 if (divisor == 0 || dividend == Integer.MIN_VALUE && divisor == -1)10 return Integer.MAX_VALUE;11 int res = 0;12 int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1; // 异或运算，除数和被除数同号为正，异号为负13 long dvd = Math.abs((long) dividend);14 long dvs = Math.abs((long) divisor);15 while (dvd >= dvs) {16 dvd -= dvs;17 res++;18 }19 return sign == 1 ? res : -res;20 }21 }
思路二：采用位移运算，任何一个整数可以表示成以2的幂为底的一组基的线性组合，即num=a_0*2^0+a_1*2^1+a_2*2^2+...+a_n*2^n。基于以上这个公式以及左移一位相当于乘以2，我们先让除数左移直到大于被除数之前得到一个最大的基。然后接下来我们每次尝试减去这个基，如果可以则结果增加加2^k,然后基继续右移迭代，直到基为0为止。因为这个方法的迭代次数是按2的幂直到超过结果，所以时间复杂度为O(logn)。
1 public class DivideTwoIntegers29 { 2 public static void main(String[] args) { 3 System.out.println(divided(-36, -3)); 4 } 5 6 public static int divide(int dividend, int divisor) { 7 if (divisor == 0 || dividend == Integer.MIN_VALUE && divisor == -1) 8 return Integer.MAX_VALUE; 9 int res = 0;10 int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1; // 异或运算，除数和被除数同号为正，异号为负11 long dvd = Math.abs((long) dividend);12 long dvs = Math.abs((long) divisor);13 while (dvs <= dvd) {14 long temp = dvs, mul = 1;15 while (dvd >= temp << 1) { // temp<<1，二进制表示左移一位，等价于temp乘以216 temp = temp << 1;17 mul = mul << 1;18 System.out.println("temp = " + temp + " " + "mul = " + mul);19 }20 dvd -= temp;21 System.out.println("dvd" + dvd);22 res += mul;23 }24 return sign == 1 ? res : -res;25 }26 }