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

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).