首页 > 代码库 > [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 + 二分法 )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。