【29】Divide Two Integers

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

If it is overflow, return MAX_INT.

不能用乘除就只能用减法了，当然如果一个一个减的话显然太慢了，所以借住移位操作，每次减去一个被除数经过移位后能减的最大的数。 int divide(int dividend, int divisor) { if(divisor==0)return INT_MAX; long res=0; bool f; if(dividend<0&&divisor<0 || dividend>0&&divisor>0)f=1; else f=0; long dividends=abs((long)dividend); long divisors=abs((long)divisor); int k=0; long tmp=divisors; while(tmp<=dividends) { tmp=(tmp<<1); k++; } for(int i=k-1;i>=0;i--) { long tmp=(divisors<<i); if(tmp<=dividends){ res+=((long)1<<i); dividends-=tmp; } } if(!f)res=-res; if(res>INT_MAX)return INT_MAX; return res; }