给定两个整数，被除数 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
提示：
被除数和除数均为 32 位有符号整数。 除数不为 0。 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
解析：
方式一：
可以用迭代，被除数 -= 除数
如下，超时
代码语言：javascript复制public class leetcode29 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int dividend = -2147483648;int divisor = 2;
System.out.println(divide(dividend,divisor));
}
//超时
public static int divide(int dividend,int divisor){
if(dividend==0){
return 0;
}
if(divisor==1) return dividend;
if(divisor==-1){
if(dividend>Integer.MIN_VALUE){
return -dividend;
}
return Integer.MAX_VALUE;
}
boolean sign = (dividend>0&&divisor>0)||(dividend<0&&divisor<0);
// long first = dividend>0?dividend:-dividend;//该写法答案不对
// long second = divisor>0?divisor:-divisor;//该写法答案不对
long first = dividend;
int second = divisor;
first = first>0?first:-first;
second = second>0?second:-second;
long ans = div(first,second);
if(sign){
return ans>Integer.MAX_VALUE?Integer.MAX_VALUE:(int)ans;
}
return (int)(-ans);
}
public static long div(long first,long second){
long ans = 0;
while(first>=second){
first -= second;
ans ;
}
return ans;
}
}另外一种优化后的方法，可用
代码语言：javascript复制
public static int divide(int dividend,int divisor){
if(dividend==0) return 0;
if(divisor==1) return dividend;
if(divisor==-1){
//只要比最小值大（即不是最小整数），都直接返回相反数即可
if(dividend>Integer.MIN_VALUE) return -dividend;
//如果是最小的整数，就返回最大的整数
return Integer.MAX_VALUE;
}
long a = dividend;
long b = divisor;
int sign = 1;
if((a>0&&b<0)||(a<0&&b>0)){
sign = -1;
}
a = a>0?a:-a;
b = b>0?b:-b;
long res = div(a,b);
if(sign>0){
return (int) (res>Integer.MAX_VALUE?Integer.MAX_VALUE:res);
}
return (int) (-res);
}
static long div(long a,long b){
if(a<b) return 0;
long count = 1;
long tb = b;//在后面的代码中不更新b
while(tb tb<a){
count = count count; //最小解翻倍
tb = tb tb; //当前测试的值也翻倍
}
return count div(a-tb,b);
}
