将两个整数相除，要求不使用乘法、除法和 mod 运算符。
如果溢出，返回 2147483647 。
样例
给定被除数 = 100 ，除数 = 9，返回 11。
1.超时的二分法(里面的求和增加了复杂度)：class Solution { public: /** * @param dividend the dividend * @param divisor the divisor * @return the result */ int divide(int dividend, int divisor) { // Write your code here if(divisor==0)return 2147483647; bool flag=true; if((dividend>0&&divisor<0)||(dividend<0&&divisor>0))flag=false; long long a=llabs((long long)dividend); long long b=llabs((long long)divisor); long long sum=0; long long start=0; long long end=a; long long mid=0; while(a>=b) { sum=0; mid=(start+end)/2; for(int i=0;i<mid;i++) sum+=b; if(sum-a>0)end=mid-1; else if(a-sum>=b)start=mid+1; else break; } if(!flag)mid=-mid; if(mid>INT_MAX||mid<INT_MIN)return 2147483647; return mid; } };
2.利用二进制性质（移位操作）的巧妙方法（遇到很大的被除数像指数一样快）
class Solution { public: /** * @param dividend the dividend * @param divisor the divisor * @return the result */ int divide(int dividend, int divisor) { // Write your code here if(divisor==0)return 2147483647; bool flag=true; if((dividend>0&&divisor<0)||(dividend<0&&divisor>0))flag=false; long long a=llabs((long long)dividend); long long b=llabs((long long)divisor); long long ans=0; while(a>=b) { long long cnt=1; long long temp=b; while(a>=temp) { a-=temp; ans=ans+cnt; cnt=cnt<<1; temp=temp<<1; } } if(!flag)ans=-ans; if(ans>INT_MAX||ans<INT_MIN)return 2147483647; return ans; } };
