Problem:
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
Solution:
不能乘除就加减就行了，但是一个问题是加减有可能速度太慢，因此需要转换，由于任何一个数都能表示成二进制，所以有dividend=divisor*（a*2^1 + b*2^2 + ...... + m*2^k）
所以只要计算出所有divisor*2^k，然后减去即可。
题目大意：
给定两个整数，要求不用乘除法和取模运算，计算出a/b的值，当结果越界的时候输出INT最大值
Java源代码（260ms）：
public class Solution {public int divide(int dividend, int divisor) {long a,b,flag=0,sum=0;long[] map=new long[33],times=new long[33];if(dividend<0 && divisor<0)flag=1;else if(dividend>0 && divisor>0)flag=1;a=Math.abs((long)dividend);b=Math.abs((long)divisor);int i=0;map[0]=b;times[0]=1;while(map[i]<=a){i++;map[i]=map[i-1]+map[i-1];times[i]=times[i-1]+times[i-1];}for(int j=i-1;j>=0;j--){while(a >= map[j]){a-=map[j];sum+=times[j];}}sum=flag==1?sum:-sum;if(sum>Integer.MAX_VALUE || sum<Integer.MIN_VALUE)return Integer.MAX_VALUE;return (int)sum;}
}C语言源代码（4ms）：
long long ABS(long long a){return a>0?a:-a;
}
int divide(int dividend, int divisor) {int i=0,j,flag=0;long long sum=0,a,b,map[33],times[33],STOP=1;STOP=((long long)2147483647)+1;if(divisor==0)return INT_MAX;if(dividend==0)return 0;if((dividend>0 && divisor>0) || (dividend<0 && divisor<0))flag=1;a=ABS((long long)dividend);b=ABS((long long)divisor);map[0]=b;times[0]=1;while(map[i] <= a && i<33){i++;map[i]=map[i-1]+map[i-1];times[i]=times[i-1]+times[i-1];}for(j=i-1;j>=0;j--){while(a >= map[j]){a-=map[j];sum+=times[j];}}sum=flag?sum:-sum;if(sum<INT_MIN || sum > INT_MAX)return INT_MAX;return (int)sum;
}C++源代码（24ms）：
class Solution {
public:int divide(int dividend, int divisor) {int i=0,j,flag=0;long long sum=0,a,b,map[33],times[33],STOP=1;STOP=STOP<<31;if(divisor==0)return INT_MAX;if((dividend>0 && divisor>0) || (dividend<0 && divisor<0))flag=1;a=abs((long long)dividend);b=abs((long long)divisor);map[0]=b;times[0]=1;while(map[i] <= STOP){i++;map[i]=map[i-1]+map[i-1];times[i]=times[i-1]+times[i-1];}for(j=i-1;j>=0;j--){while(a >= map[j]){a-=map[j];sum+=times[j];}}sum=flag?sum:-sum;if(sum<INT_MIN || sum > INT_MAX)return INT_MAX;return (int)sum;}
};Python源代码（72ms）：
class Solution:# @param {integer} dividend# @param {integer} divisor# @return {integer}def divide(self, dividend, divisor):flag=0if dividend>0 and divisor>0:flag=1elif dividend<0 and divisor<0:flag=1if dividend==0:return 0dividend=abs(dividend)divisor=abs(divisor)map=[0 for i in range(33)]times=[1 for i in range(33)]i=0map[0]=divisor;times[0]=1while map[i]<=dividend:i+=1map[i]=map[i-1]+map[i-1]times[i]=times[i-1]+times[i-1]j=i-1;sum=0while j>=0:while map[j]<=dividend:dividend-=map[j]sum+=times[j]j-=1sum = -sum if flag==0 else sumif sum>2147483647:return 2147483647return sum