Leetcode---Divide Two Integers

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

整数的除法，但无法用乘号，除号和余号。

可以考虑二分，假设A/B, 则解空间在[0, A]

当B*A/2注意这里A/2可能是解，因为整数的除法是舍去余数的
当B*A/2>A时，表明解在[0, A/2)之间，
当B*A/2==A时，表明解为A/2

不断缩小解空间，最后得到解，这段code是精髓：

while(i>=j){
        long long k=(i+j)>>1;
        long long m=multiply(k,b);
        if(m>a){
            i=k-1;
        }else if(m==a){
            answer=k;
            break;
        }else{
            answer=k;
            j=k+1;
        }
    }

全部代码如下：

long long multiply(long long a, long long b){
    if(a==0)
        return 0;
    else{
        return (multiply(a>>1,b)<<1)+((a&1)?b:0);
    }
}
int f(long long a, long long b){
    int answer=0;
    long long i=a;
    long long j=0;
    while(i>=j){
        long long k=(i+j)>>1;
        long long m=multiply(k,b);
        if(m>a){
            i=k-1;
        }else if(m==a){
            answer=k;
            break;
        }else{
            answer=k;
            j=k+1;
        }
    }
    return answer;
}
    int divide(int dividend, int divisor) {
        long long a=dividend;
        long long b=divisor;
        if(a<0 && b>0)
            return -f(-a, b);
        else if(a>0 && b<0)
            return -f(a, -b);
        else if(a<0 && b<0)
            return f(-a, -b);
        else if(a>0 && b>0)
            return f(a, b);
        else if(a==0)
            return 0;
        else
            return 0xFFFFFFFF;
    }