Title:

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

If it is overflow, return MAX_INT.

这道题就是实现除法，而且不能用到乘法，除法和取余。

第一想法是利用加法，对于一般情况，被除数和除数都是正数，不断累加除数，直到除数大于被除数，这样累加的次数就是结果。

代码如下：

#include 
    
     #include 
     
      #include 
      
       int divide(int dividend, int divisor) {    long long temp;    long long len=0;    int flag=1;    int flag1=1;    if (dividend<0) {    	flag=-1;    	dividend=abs(dividend);    }    if (divisor<0) {    	flag1=-1;    	divisor=abs(divisor);    	if (divisor<0)    		return 0;    }    if(dividend
       
        =0)     	return 0;    	     if(dividend==divisor) {     	if (flag1==flag)     		return 1;     	else     		return -1;     }    	    temp=divisor;    if (dividend<0) {    	while (dividend+temp<=0) {    		temp=temp+divisor;    		len++;    		if (len>INT_MAX) {    				return (int)flag*flag1*INT_MAX;    		}    	}    return (int)flag*flag1*len;    }    else {    while(dividend-temp>=0) {    	temp=temp+divisor;    	len++;    	if (len>INT_MAX) {    		return (int)flag*flag1*INT_MAX;    	}    }   return (int)flag*flag1*len;}}
       
      
     
    

但对于一些情况会超时，比如被除数为-2147483648，除数为-1，那么相当于要累加2147483647次，时间开销过大。因此这种思路应该舍弃。

另外一种思路就是利用二进制，每一个数都可以用二进制表示，也就是dividend=divisor*(2^0,+2^1+ 2^2+2^3+....)，也就是说只要算出加到2的多少次方，然后把前面的都累加即可。

代码如下：

solution：

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--) {    	if (a>=map[j]) {    		a=a-map[j];    		sum=sum+times[j];    	}    }        sum=flag?sum:-sum;    if(sum
    
      INT_MAX)return INT_MAX;      return (int)sum;  }
    

首先利用两个数组map[33],times[33]存divisor*2^k，和2^k，也就是多少个divisor。map[0]=divisor，为1个divisor，times[0]=1，表示1个。

接着while循环，循环条件是，map[i]<=a,也就是循环出多少个divisor会大于dividend，然后就停止。在while循环中，用map[i]记录下2*divisor, 4*divisor, 8*divisor....

用times[i]记录下2, 4 ,8....也就是次数。

然后在for循环中，进行相减运算，从最大的map开始算，这里j=i-1，是表示map中最大的没有超过a的数，因为在上个while循环中，当map[i]>a时，map[i]已经存入数组了。因此要i-1，表示小一点的元素。如果dividend大于等于map[j]的话，dividend就减掉这个元素，同时，sum加上对应的次数times[j]，也就是map[j]等于多少个divisor。