# 22ms c++ code use binarysearch and quickmultiply

• 1.except the sign of dividend and divisor
let a = dividend and b = divisor
we want to know the ans = a/b
and except the overflow
the range of ans must be 0 ~ INT_MAX
so we can find ans in range 0~INT_MAX use binarysearch
if ans is out of the range,so we return INT_MAX
suppose b equal 11 = 1011B a equal 3
b = 11a + 12a + 04a + 18a

``````class Solution {
public:
long long qmul(long long  a,long long  b){ //a*b
long long ans = 0;
for(;b>0;b>>=1,a+=a) if(b&1) ans+=a;
return ans;
}
int divide(int dividend, int divisor) {
long long ans;
long long left = 0;
long long right = (long long)INT_MAX+10;
long long mid = 0;
if(divisor == 0) return INT_MAX;
if(dividend == 0) return 0;
long long divisor_tmp = divisor;
long long dividend_tmp = dividend;
bool flag = ((long long)divisor*dividend < 0);
divisor_tmp = divisor_tmp < 0 ? -divisor_tmp : divisor_tmp;
dividend_tmp = dividend_tmp < 0 ? - dividend_tmp: dividend_tmp;
while(right - left > (long long)1 ){
//printf("%lld %lld\n",left,right);
mid = ( left + right ) >> 1;
if( qmul(mid,divisor_tmp) <= dividend_tmp)
left = mid;
else
right = mid;
}
ans = left;
if(flag) ans = -ans;
if(ans < INT_MIN || ans > INT_MAX)
ans = INT_MAX;
return (int)ans;
};
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.