# 29. Divide Two Integers

## problem description

Given two integers `dividend` and `divisor`, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing `dividend` by `divisor`.

The integer division should truncate toward zero.

**Example 1:**

```
Input: dividend = 10, divisor = 3
Output: 3
```

**Example 2:**

```
Input: dividend = 7, divisor = -3
Output: -2
```

## algorithm thought

记得csapp专门有一门实验就跟这个题目很类似。比如不用哪些符号实现其他的符号啥的。这里就是不用乘除取余数，实现除法。能用的还有加法和减法，除法其实就是看被除数中能减去几个除数。想到这一步就很清晰了，直接诶一直减去除数就行。但是这样有的慢，可以减去除数的倍数，这样会快一点。直接移位最好，就能很快生成2的倍数

注意会有一种情况超过INT\_MAX,那就是INT\_MIN/-1的时候，这种情况要单独考虑下

## code

```cpp
class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend==INT_MIN&&divisor==-1)
            return INT_MAX;
        long dd=labs(dividend);
        long di=labs(divisor);
        long res=0;
        while(dd>=di){
            long tmp=di, m=1;
            while(tmp<<1<=dd){
                tmp=tmp<<1;
                m=m<<1;
            }
            dd-=tmp;
            res+=m;
        }
        return dividend>0^divisor>0?-res:res;
    }
};
```

## algorithm analysis

虽然有个循环，但是每次tmp都是乘2扩展，所以时间复杂度是O(1).

