当前位置 博文首页 > 龚厂长的博客：leetcode-29. 两数相除
题目：两数相除
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333…) = truncate(3) = 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333…) = -2
解析：
开始看到这个题目的时候，我首先想到的是将除数不停的相加，直到大于被除数，那么除数相加的次数就是结果。很快按照这个思路写好了代码，提交上去，报了超时。经过分析意识到如果除数的绝对值很小，被除数的绝对值很大的话，那么相加的次数是非常大的，比如除数是1，被除数是-2147483648，那么需要循环相加2147483648次才能得到结果，这就很容易超时了。
后来整理思路，拿出小学学习的除法运算，手算了一遍，发现了规律。
下面以75/3为例介绍。
75/3=25，25换算到二进制是25=11001=24+23+20，75=3*24 + 3*23+3*20 ，由此我们可以知道让3不停的翻倍，3,6,12…，直到最接近75但是比75小的数，这样翻倍的次数，就是商的二进制表示里面最高位的1所在位置，上面这个例子，最高位的1位于4号位，之后用75-3*24=27，然后以27为被除数，也是让3不停的翻倍，直到最接近27但是比27小的数，翻倍的次数，就是商的二进制表示里面次高位的1所在位置，这样依次下去，便可以得到商的每一位。
我们知道让数字翻倍最简单的办法就向左移一位，因此可以借助位运算来翻倍。
根据上面的原理代码如下：
public int divide(int dividend, int divisor) {
if(dividend==0){
return 0;
}
long ldividend=dividend,ldivisor=divisor;
long res=0;//表示商
boolean positive=true;
if(ldividend<0&&ldivisor>0||ldividend>0&&divisor<0){
positive=false;
}
//将负数值全部转换为正数，正数便于计算
if(ldividend<0){
ldividend=-ldividend;
}
if(divisor<0){
ldivisor=-ldivisor;
}
while(ldividend>=ldivisor){
//计算商里面每个1的位置
int bit=shiftBit(ldividend,ldivisor);
ldividend=ldividend-(ldivisor<<bit);
res=res|(1L<<bit);
if(positive){
if(res>Integer.MAX_VALUE){
return Integer.MAX_VALUE;
}
}else{
if(-res<Integer.MIN_VALUE){
return Integer.MAX_VALUE;
}
}
}
if(!positive){
return (int)-res;
}else{
return (int)res;
}
}
//计算商里面每个1的位置
private int shiftBit(long a,long b){
int bit=0;
while(a>=(b<<1)){
bit++;
b=b<<1;
}
return bit;
}
运行结果：
