# [leetcode] Divide Two Integers

### Divide Two Integers

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

If it is overflow, return MAX_INT.

tags: math, binary search

8/10/2015 update

```class Solution {
public:
int divide(int dividend, int divisor) {
int flag = 1;
long ldividend = dividend;
long ldivisor = divisor;
if(ldividend < 0){
ldividend = -ldividend;
flag *= -1;
}
if(ldivisor < 0){
ldivisor *= -1;
flag *= -1;
}
long quotient = 0;
while(ldividend >= ldivisor){
long thisQuotient = 1;
long d = ldivisor;
while(d <= ldividend){
d = d << 1;
thisQuotient = thisQuotient << 1;
}
d = d >> 1;
thisQuotient = thisQuotient >> 1;
ldividend -= d;
quotient += thisQuotient;
}
quotient *= flag;
if(quotient == (long)0x80000000){
return 0x7fffffff;
}
else{
return quotient;
}
}
};```

tag中的binarysearch应该值在移位dividend时，通过比较reminder和divisor的大小决定给quotient赋值1还是0.

```class Solution {
public:
int divide(int dividend, int divisor) {
int flag = 1;
int overflow = 0;
if(divisor == 0){
return INT_MAX;
}
if(dividend == 0x80000000){// minimal 32-bit integer
if(divisor == -1){
return INT_MAX;//overflow
}
else{
dividend = 0x7FFFFFFF;
overflow = 1;
flag *= -1;
}
}
else if(dividend < 0){
dividend *= -1;
flag *= -1;
}
if(divisor == 0x80000000){// minimal 32-bit integer
if(dividend == 0x7FFFFFFF && overflow == 1){
return 1; // 0x80000000 / 0x80000000
}
else{
return 0;//any other 32-bit integers divided by 0x80000000 would be 0
}
}
else if(divisor < 0){
divisor *= -1;
flag *= -1;
}

//article begin
int bit = 0x40000000;
int reminder = 0;
int quotient = 0;
while(bit > 0){
reminder = reminder << 1;
if((bit & dividend) > 0){//parenthese is IMPORTANT!
reminder += 1;
}
bit = bit >> 1;
if(reminder >= divisor){
reminder -= divisor;
quotient = quotient << 1;
quotient += 1;
}
else{
quotient = quotient << 1;
}
}

//deal with overflow and flag
reminder += overflow;
if(reminder >= divisor){
quotient += 1;//no need to shift
}
quotient *= flag;
return quotient;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.