首页 > 代码库 > Leetcode--Divide Two Integers
Leetcode--Divide Two Integers
Problem Description:
Divide two integers without using multiplication, division and mod operator.
分析:题目意思很容易理解,就是不用乘除法和模运算求来做除法,很容易想到的一个方法是一直做减法,然后计数,但是提交之后显示超时,在网上找到一种解法,利用位运算,意思是任何一个整数可以表示成以2的幂为底的一组基的线性组合,即num=a_0*2^0+a_1*2^1+a_2*2^2+...+a_n*2^n。基于以上这个公式以及左移一位相当于乘以2,我们先让除数左移直到大于被除数之前得到一个最大的基n的值,说明被除数中至少包含2^n个除数,然后减去这个基数,再依次找到n-1,...,1的值。将所有的基数相加即可得到结果。具体代码如下:
class Solution { public: int divide(int dividend, int divisor) { assert(divisor != 0); int res=0; int flag=1; if((dividend<0 && divisor>0)||(dividend>0 && divisor<0)) flag=-1; long long divid=abs((long long)dividend);//考虑对最大最小整数取模的情况 long long divi=abs((long long)divisor); long long temp=0; while(divi<=divid) { int cnt=1; temp=divi; while((temp<<=1)<=divid) { cnt<<=1; } res+=cnt; divid-=(temp>>1); } return (int)res*flag; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。