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 = 3Output: 3Example 2:
Input: dividend = 7, divisor = -3Output: -2只要理解了计算机中除法的原理,模拟思路就可以处理的比较好。
麻烦之处在于边界的处理上。
超帅的金毛: 模拟计算机中的除法操作。
AC代码如下: 16ms
class Solution { public int divide(int dividend, int divisor) { if(dividend==Integer.MIN_VALUE&&divisor==-1) return Integer.MAX_VALUE; boolean flag=dividend>0&&divisor>0||dividend<0&&divisor<0; long absDividend=Math.abs((long)dividend); long absDivisor=Math.abs((long)divisor); int ans=0; long remainder=0; int len=getLength(absDividend); while(len>0){ int bit=getBit(absDividend,len--); remainder=(remainder<<1)+bit; if(remainder<absDivisor) ans=ans<<1; else{ ans=(ans<<1)+1; remainder=remainder-absDivisor; } } return flag?ans:-ans; } public int getLength(long num){ int len=0; while(num!=0){ num=num>>1; len++; } return len; } public int getBit(long num,int index){ int i=index-1; if(((num&(1<<i))>>i)==1) return 1; else return 0; }}如果看代码比较吃力的话,充电链接:计算机计算乘除法的原理。
害怕的黄蜂: 在网上找到一种解法,利用位运算,意思是任何一个整数可以表示成以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的值。将所有的基数相加即可得到结果。
具体代码如下: 24ms
class Solution { public int divide(int dividend, int divisor) { if(dividend==Integer.MIN_VALUE&&divisor==-1) return Integer.MAX_VALUE; boolean flag=dividend>0&&divisor>0||dividend<0&&divisor<0; long m=Math.abs((long)dividend); long n=Math.abs((long)divisor); int ans=0; while(m>=n){ long temp=n; int count=1; while(m>=(temp<<1)){ temp=temp<<1; count=count<<1; } ans=ans+count; m=m-temp; } return flag?ans:-ans; } }