首页 > 代码库 > [LeetCode] Divide Two Integers( bit + 二分法 )

[LeetCode] Divide Two Integers( bit + 二分法 )

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

常常出现大的负数,无法用abs()转换成正数的情况

class Solution{private:    vector<long long> f;public:    int bsearch(vector<long long> &a,int left,int right,long long key){        if(left > right)            return -1;        int mid = left + (right-left)/2;        if(a[mid]==key)            return mid;        else if(a[mid]<key){           int pos = bsearch(a,mid+1,right,key);           return pos == -1 ?mid :pos;        }else            return bsearch(a,left,mid-1,key);    }    int divide(int devidend,int divisor){        int sign = devidend <0 ?-1:1;        if(divisor<0)            sign *= -1;        long long div = devidend;        div = abs(div);        long long divisorL = divisor;        divisorL = abs(divisorL);        f.push_back(divisorL);        int size = 1;        while(true){            if(f[size-1] >= div)                break;            f.push_back(f[size-1]+f[size-1]);            size++;        }//end while        int num = 0;        long long sum = 0;        while(div>0){           int pos = bsearch(f,0,size-1,div);           if(pos == -1)               break;           div -= f[pos];           num += (1<< pos);        }//end while       return num*sign;    }};

 

[LeetCode] Divide Two Integers( bit + 二分法 )