不使用乘法、除法或mod,实现两数相除解法一：每次自增除数解法二解法三

60 阅读 0 评论 40 点赞

我是靠谱客的博主活力大山，最近开发中收集的这篇文章主要介绍不使用乘法、除法或mod,实现两数相除解法一：每次自增除数解法二解法三，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

被除数÷除数=商+余数
需要注意的问题：

int 的范围是[-2^31,2^31-1],也就是【-2147483648，2147483647】，如果-2147483648/-1结果会超出int 范围。
除法，乘法和mod都不能使用，那可以使用加减，移位。
只需保留商即可
保证数据在int范围。

电脑做二进制除法的时候，是让被除数连续减去几次除数（减去n倍除数），直到差小于除数时为止，这样减去的次数就是商，剩下的差就是余数。
可以借鉴这个思想。

解法一：每次自增除数

当然被除数减去除数也可以。
如 10/3，除数自增，10在【3+3+3，3+3+3+3】范围里面。
如果被除数取得很大，除数取得很小，那么会很慢。（二者同号情况下）
下面代码有个错误，就是int会溢出。

class Solution {
public int divide(int dividend, int divisor) {
if(dividend==0) return 0;
if(dividend==Integer.MIN_VALUE&&divisor==-1){
return Integer.MAX_VALUE;
}
int ans=1;//商
int f=-1;//两个数是否异号
if(dividend<0&&divisor<0||dividend>0&&divisor>0) f=1;
if(f==-1){
//异号的话，全部变为正数。
dividend=Math.abs(dividend);
divisor=Math.abs(divisor);
}
int temp=0;
int d=divisor;
while(true){
if(divisor==dividend) return f==-1?-ans:ans;
if(divisor>dividend&&temp<dividend){
//找到结果
ans--;
return f==-1?-ans:ans;
}
temp=divisor;
divisor+=d;
ans++;
}
}
}

解法二

注意Math.abs()源码

public static int abs(int a) {
return (a < 0) ? -a : a;
}
****************************************
public static long abs(long a) {
return (a < 0) ? -a : a;
}
所以参数需要强转一下。

用dividend/2^n来减少减法的次数。（加法和减法的原理一样）
当dividend/2^n>=divisor的时候，说明dividend-divisor*2^n>=0，
于是可以用dividend-=divisor*2^n来简化。
这样每次最多循环32次。

class Solution {
public int divide(int dividend, int divisor) {
if(dividend==0) return 0;
if(dividend==Integer.MIN_VALUE&&divisor==-1) return Integer.MAX_VALUE;
int ans=0;
int f=-1;
if(dividend<0&&divisor<0||dividend>0&&divisor>0) f=1;
long c_divisor=Math.abs((long)divisor);
long c_dividend=Math.abs((long)dividend);
for(int i=31;i>=0;i--){
if((c_dividend>>i)>=c_divisor){
ans+=(1<<i);
c_dividend=c_dividend-(c_divisor<<i);
}
}
return f*ans;
}
}

那这个算法的正确性如何呢？
解法二和解法三一个是>>，一个是<<。
道理一样。

解法三

大致思路：每次让dividend=dividend-n*divisor(且每次的n取值尽可能大)
此题限制，我们可以用位移运算，此时的n一定是2的倍数。那么和解法二差不多。
所以首先让diviosor>dividend,然后开始计算。

class Solution {
public int divide(int dividend, int divisor) {
if(dividend==0) return 0;
if(dividend==Integer.MIN_VALUE&&divisor==-1) return Integer.MAX_VALUE;
int ans=0;
int f=-1;
if(dividend<0&&divisor<0||dividend>0&&divisor>0) f=1;
long c_divisor=Math.abs((long)divisor);
long c_dividend=Math.abs((long)dividend);
int count=0;
while(c_divisor<=c_dividend){
//使c_divisor大于c_dividend
count++;
c_divisor=c_divisor<<1;//这里如果不使用log就会溢出。
}
while(count>0){
count--;
c_divisor=c_divisor>>1;
if(c_divisor<=c_dividend){
ans+=1<<count;
c_dividend-=c_divisor;
}
}
return f*ans;
}
}

当然注意题目所说的数据都是int范围的，所以不用long

class Solution {
public int divide(int dividend, int divisor) {
if(dividend==0) return 0;
if(dividend==Integer.MIN_VALUE&&divisor==-1) return Integer.MAX_VALUE;
int ans=0;
int f=-1;
if(dividend<0&&divisor<0||dividend>0&&divisor>0) f=1;
if(dividend==Integer.MIN_VALUE) {
if (divisor < 0) {
dividend -= divisor;
ans++;
} else {
dividend += divisor;
ans++;
}
if(dividend==0) return ans*f;
}else if(divisor==Integer.MIN_VALUE) return 0;
int c_divisor=Math.abs(divisor);
int c_dividend=Math.abs(dividend);
for(int i=31;i>=0;i--){
if((c_dividend>>i)>=c_divisor){
ans+=(1<<i);
//System.out.println(ans);
c_dividend=c_dividend-(c_divisor<<i);
}
}
return f*ans;
}
}