两数相除__牛客网

C/C++

油头教授的坩埚

In this problem, we are asked to divide two integers. However, we are not allowed to use division, multiplication and mod operations. So, what else can we use? Yeah, bit manipulations.

Let's do an example and see how bit manipulations work.

Suppose we want to divide 15 by 3, so 15 is dividend and 3 is divisor. Well, division simply requires us to find how many times we can subtract the divisor from the the dividend without making the dividend negative.

Let's get started. We subtract 3 from 15 and we get 12, which is positive. Let's try to subtract more. Well, we shift 3 to the left by 1 bit and we get 6. Subtracting 6 from 15 still gives a positive result. Well, we shift again and get 12. We subtract 12 from 15 and it is still positive. We shift again, obtaining 24 and we know we can at most subtract 12. Well, since 12 is obtained by shifting 3 to left twice, we know it is 4times of 3. How do we obtain this 4? Well, we start from 1 and shift it to left twice at the same time. We add 4 to an answer (initialized to be 0). In fact, the above process is like 15 = 3 * 4 + 3. We now get part of the quotient (4), with a remainder 3.

Then we repeat the above process again. We subtract divisor = 3 from the remaining dividend = 3 and obtain 0. We know we are done. No shift happens, so we simply add 1 << 0 to the answer.

Now we have the full algorithm to perform division.

According to the problem statement, we need to handle some exceptions, such as overflow.

Well, two cases may cause overflow:

divisor = 0;
dividend = INT_MIN and divisor = -1 (because abs(INT_MIN) = INT_MAX + 1).

Of course, we also need to take the sign into considerations, which is relatively easy.

Putting all these together, we have the following code.

class Solution { public: int divide(int dividend, int divisor) {
        if (!divisor || (dividend == INT_MIN && divisor == -1))
            return INT_MAX; int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1; long long dvd = labs(dividend);  long long dvs = labs(divisor);  int res = 0; while (dvd >= dvs) { 
            long long temp = dvs, multiple = 1; while (dvd >= (temp << 1)) {
                temp <<= 1; multiple <<= 1; }
            dvd -= temp; res += multiple;  }
        return sign == 1 ? res : -res;  }
};

发表于 2017-03-12 23:16:56 回复(5)

anas

class Solution {
public:
    int divide(int dividend, int divisor) {
        long long a = abs((long long)dividend);  
        long long b = abs((long long)divisor);  
  		int finalcount=0;
        while(a >= b){
           int count = 1;

            long sum = b;
            while(sum + sum <= a){
                sum += sum;
                count += count;
            }
            a -= sum;
            finalcount += count;
        };
        
        return (dividend>>31 ^ divisor>>31)? -finalcount:finalcount;  
    }
};                               


使用一般的减法运算，很容易导致超时；
为了减少做减法的次数，是用成倍的加法操作可以。

发表于 2016-07-17 14:39:14 回复(4)

元气の悟空

class Solution {
public:
    int divide(int dividend, int divisor) {
        return dividend/divisor;
    }
};//你叫我不用  我就真的不用？

编辑于 2016-09-09 20:42:55 回复(13)

啊哟嘿

要学会举一反三，除了除法，加法你会嘛？减法你会嘛？成法你会吗？这里不使用“+、-、*、%”来实现加减乘除

public int add(int a, int b) {
        int sum = a;
        int arr = b;// 表示进位
        while (arr != 0) {
            sum = a ^ b;
            arr = (a & b) << 1;
            a = sum;
            b = arr;
        }
        return sum;
    }

    public int minus(int a, int b) {
        // b为减数,先变成负数
        b = add(~b, 1);
        return add(a, b);
    }

    public int multi(int a, int b) {
        // b为乘数
        for (int i = 0; i < b - 1; i++) {
            a = add(a, a);
        }
        return a;
    }

    public int divide(int dividend, int divisor) {
        // a被除树，b为除数
        int a = dividend;
        int b = divisor;
        if(a==1)
            return 0;
        if(b==0)
            try {
                throw new Exception("被除数不能为0！");
            } catch (Exception e) {
                e.printStackTrace();
                return 0;
            }
        int result = 0;
        if (a > 0 && b > 0) {
            while (a > 0) {
                a = minus(a, b);
                if (a >= 0)
                    result++;
            }
            return result;
        } else if (a < 0 && b > 0) {
            a = add(~a, 1);
            return add(~divide(a, b), 1);// 结果变为负号
        } else if (a > 0 && b < 0) {
            b = add(~b, 1);
            return add(~divide(a, b), 1);
        } else if (a < 0 && b < 0) {
            a = add(~a, 1);
            b = add(~b, 1);
            return divide(a, b);
        }
        return result;
    }

发表于 2017-12-25 17:27:52 回复(3)

洁白

关键思想:算出a/b二进制形式的结果

  public int divide(int d1, int d2) {
        // 如果没有(long)d1, 对Integer.MIN_VALUE求绝对值会溢出,像(-128,127)
        long nd1 = Math.abs((long)d1);
        long nd2 = Math.abs((long)d2);
        if (nd2 == 0) {
            return 0;
        }
        int count = 0;
        while (nd1 >= nd2) {
            // 如果不是long,temp << 1,这一步有可能溢出
            long temp = nd2;
            int power = 1;
            while (nd1 >= temp << 1) {
                temp = temp << 1;
                power = power << 1;
            }
            nd1 -= temp;
            count += power;
        }
        //无符号右移31位,才能把符号位移到该数的最低位,再做异或操作
        return (d1 >>> 31 ^ d2 >>> 31) == 1 ? -count : count;
    }

发表于 2019-06-06 15:27:22 回复(0)

JacobGo！

public int divide(int dividend, int divisor) {
		// 结果的符号
		int flag = 1;
		if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0))
			flag = -1;
		//把除数和被除数转化为正数进行判断
		long ldividend = Math.abs((long) dividend);
		long ldivisor = Math.abs((long) divisor);
		if (ldividend == 0 || ldividend < ldivisor)
			return 0;
		if (ldivisor == 0)
			return Integer.MAX_VALUE;

		long res = solve(ldividend, ldivisor);
		int ans;
		//如果结果溢出，根据符号输出相应的值
		if (res > Integer.MAX_VALUE)
			ans = flag == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
		else
			ans = (int) (flag * res);
		return ans;
	}

	private long solve(long ldividend, long ldivisor) {
		if(ldividend<ldivisor)
			return 0;
		long res = 1;
		long sum = ldivisor;
		//为防止进行多次重复的计算，每一次循环除数*2
		while (sum + sum <= ldividend) {
			sum += sum;
			res += res;
		}
		return res + solve(ldividend - sum, ldivisor);
	}

发表于 2017-07-30 10:36:35 回复(0)

风中追风20180314092925

参考网上别人代码，将因子不断乘以2（可以通过移位实现，同时结果也从1开始不断移位加倍），然后和被除数比较，等到大于被除数一半了，就从被除数中减去，将因子个数叠加入结果中。然后在剩下的被除数中采用同样的方法减去小于其一半的因子和，循环往复。

int divide(int dividend, int divisor) {
    if(dividend == INT_MIN && divisor == -1) return INT_MAX;
    //m被除数n除数 m/n = res商
    long long m = abs((long long)dividend), n = abs((long long)divisor), res = 0;
    int flag = ((dividend > 0) ^ (divisor > 0)) ? -1 : 1;
    //规定不能用乘法
    if(divisor == 1) return (flag == 1 ? m : -m);
    while (m >= n) {
        long long temp_divisor = n, temp_res = 1;
        while (m >= (temp_divisor << 1)) {
            temp_divisor <<= 1;
            temp_res <<= 1;
        }
        res += temp_res;
        m -= temp_divisor;
    }
    return (flag == 1 ? res : -res);
}

发表于 2019-05-29 09:53:46 回复(0)

llch__

    public int divide(int dividend, int divisor) {
       if(divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1)) return Integer.MAX_VALUE;
       int sign = ((dividend<0)^(divisor<0)) ? -1 : 1;       
       int result = 0;
       long dvd = Math.abs((long)dividend);  //先转long，不然 abs(Integer.MIN_VALUE) = Integer.MIN_VALUE 且会超时
       long dsr = Math.abs((long)divisor);
       while(dsr <= dvd){
           long tmp = dsr;
           int factor = 1;
           while(dvd > tmp){
                  if(dvd < (tmp << 1)) break;  
                  tmp <<= 1;
               factor <<= 1;  
           }
           result += factor;
           dvd = dvd - tmp;
           }
        return sign > 0 ? result : -result;//规定不能乘
    }

发表于 2018-08-05 16:09:15 回复(2)

C/C++

努力的牛牛

    /*
    * 目的：不使用乘除取余操作完成除法运算
    * 方法：使用一般的减法运算，很容易导致超时；
    * 为了减少做减法的次数，是用成倍的加法操作可以。
    */
    int divide(int dividend, int divisor) {
        if (dividend==0||divisor ==0) return 0;
        long long a = abs((long long)dividend);
        long long b = abs((long long)divisor);
        int res = 0;
        while(a>=b){
            int count = 1;
            long sum = b;
            while(sum+sum<=a){
                sum+=sum;
                count+=count;
            }
            res+=count;
            a-=sum;
        }
        if ((dividend<0)^(divisor<0)){
            res=-res;
        }
        return res;
    }

发表于 2019-12-10 21:02:56 回复(0)

小河沟大河沟

- 需要注意先类型转换，labs()可以AC过，但是VS2013上绝对值还是负值，所以先类型转换成long long ,再用llabs()

class Solution_29 { //此题保证一定除尽的条件
public:
   int divide(int dividend, int divisor) {

       if (divisor == 0||(dividend==INT_MIN&&divisor==-1)) //考虑越界的问题
       {
           return INT_MAX;
       }
       int ret = 0;
       bool sign = (dividend > 0) ^ (divisor > 0); //异号为1

       //long long dividend_ = labs(dividend); //转换 abs(-2147483648)=-2147483648 ;换成labs在leetcode AC过但是VS2013编译器还是负数
       //long long divisor_ = labs(divisor); //区别lab，abs,fabs()

       long long dividend_ = llabs(long long(dividend)); //转换 abs(-2147483648)=-2147483648 //强制类型转换一个long和int 一样的，必须有两个long long
       long long divisor_ = llabs(divisor); //区别lab，abs,fabs()
       while (dividend_>=divisor_)
       {
           int temp = divisor_;
           int multi = 1;//被除数的次数
           while (dividend_ >= (temp << 1)) //成倍的增加，时间更快
           {
               temp=temp << 1;
               multi=multi << 1;
           }
           dividend_ -= temp;
           ret += multi;
       }

       return sign?-ret:ret;
   }
};

发表于 2018-01-26 10:43:37 回复(1)

C/C++

黄汉韬


class Solution {
public:
    int divide(int dividend, int divisor) {
        bool is_positive_num = true;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
            is_positive_num = false;
        }
        long divend = abs((long)dividend);
        long divor = abs((long)divisor);
        if (divend < divor) {
            return 0;
        }

        long temp = divor;

        long sum = 0;
        long num = 0;

        while (sum < divend) {
            if (sum + temp > divend) {
                if (divend - sum < divor) {
                    if (is_positive_num) {
                        return num;
                    }
                    else {
                        return -num;
                    }
                }
                else {
                    temp = divor;
                }
            }
            sum += temp;
            num += (temp / divor);
            temp = (temp << 1);

            if (sum == divend) {
                if (is_positive_num) {
                    if (num > INT_MAX) {
                        return INT_MAX;
                    }
                    else {
                        return num;
                    }
                }
                else {
                    return -num;
                }
            }
        }
    }
};

发表于 2017-12-05 18:59:21 回复(0)

C/C++

nbgao

class Solution {
public:
    int divide(int dividend, int divisor) {
    	if(divisor == 0)
    		return INT_MAX;
    		
        long long result=0,flag=0;
		if((dividend<0)^(divisor<0))
			flag=1;
		
		long long a = abs(dividend), b = abs(divisor);
		while(a >= b)
		{
			long long k = 1, t = b;
			while(a >= t)
			{
				a -= t;
				result += k;
				k <<= 1;
				t += t; 
			}
		}
		return flag?-result:result;
    }
};

发表于 2017-09-04 01:15:11 回复(0)

sky_

class Solution {
public:
    int divide(long long a,long long  b) {
        long long k=0,ans=0,flag=0;
        if(a<0&&b>0||a>0&&b<0) flag=1;
        a=abs(a);b=abs(b);
        while(a>=b) {
             long long  k=1,tmp=b;
             while(a>=tmp) {
                a-=tmp;
                ans+=k;
                k*=2;
                tmp+=tmp; 
             }
        }
        return flag?-ans:ans;
    }
};

发表于 2017-08-23 15:30:08 回复(0)

LinuX18

// 百度到的大神正确解法
class Solution {
public:
    int divide(int dividend, int divisor) 
    {
     if(divisor == 0)
        return INT_MAX;
    int flag = (dividend<0)^(divisor<0) ? -1 : 1;
    long long diviD = labs(dividend),diviS = labs(divisor);
    int res = 0;
    while(diviD >= diviS)
    {
        long long sub = diviS,k=1;
        while((sub<<1) <= diviD)
        {
            sub <<= 1;
            k <<= 1;
        }
        diviD -= sub;
        res += k;
    }
    return res*flag;
    }
};

发表于 2017-07-12 21:42:41 回复(0)

C/C++

ButterFlyEffect

被int坑了一下，会溢出😂

class Solution {
public:
    int divide(int dividend, int divisor) {
        bool f1 = (dividend >= 0);
        bool f2 = (divisor >= 0);
        long N = abs((long)dividend);
        long M = abs((long)divisor);
        int r = 0;
        if(M == 0) return -1;
        while(N >= M) {
            long t = M, r1 = 1;
            while((t<<1) <= N) {
                t <<= 1;
                r1 <<= 1;
            }
            r += r1;
            N -= t;
        }
        return (f1==f2) ? r : -r;
    }
};

发表于 2020-12-15 14:25:32 回复(0)

羊飞飞

import java.util.*;
import java.math.BigInteger;


public class Solution {
    /**
     * 
     * @param dividend int整型 
     * @param divisor int整型 
     * @return int整型
     */
    public int divide (int dividend, int divisor) {
        // write code here
        String dd=dividend+"";
        String dv=divisor+"";
        BigInteger B=new BigInteger(dd);
        BigInteger C=new BigInteger(dv);
        B=B.divide(C);
        return Integer.parseInt(B.toString());
    }
}//掩耳盗铃法

发表于 2020-09-17 10:30:51 回复(0)

Aileon

class Solution:
    def divide(self , dividend , divisor ):
        # write code here
        if (dividend>=0 and divisor>0)&nbs***bsp;(dividend<= 0 and divisor<0): # 记录正负号
            symbol = 1
        else:
            symbol = -1
        
        if dividend < 0: # 都转成正数
            dividend = -dividend
        if divisor < 0:
            divisor = -divisor
        

        if dividend < divisor: # 被除数小于除数则直接返回0
            return 0
        def div(x,y): # 递归
            if x < y: # 如果小于除数就直接返回0
                return 0
            tmp = 1
            while x>=y: # 除数左移看看能最多移动多少位，至少1倍
                y <<= 1
                tmp <<= 1
            y >>= 1
            tmp >>= 1
            return tmp + div(x-y,divisor)
        
        res = div(dividend, divisor)
        return res if symbol > 0 else -res

发表于 2020-08-31 17:30:50 回复(0)

Python

黄沙遮天

如果是用的单处的方法，每次只减去除数的话，可能需要进行的循环次数会太多，所以在这里采用的方法是减去除数乘以2的倍数的形式，这样即使被除数很大，也会由于指数的增大，而降低一定程度的循环次数

class Solution:
    def divide(self, dividend, divisor):
        # write code here
        ops=1
        if (dividend>0 and divisor<0)&nbs***bsp;(dividend<0 and divisor>0):
            ops=-1
        dividend,divisor=abs(dividend),abs(divisor)
        count=0
        m=divisor
        while(dividend>=m):
            dividend-=m
            count+=1
            if dividend>=2*m:
                m=m*2
                count*=2
        return count*ops

发表于 2020-08-26 23:33:25 回复(0)

华科不平凡

两种方法：

辗转相减法（普通版，耗时684ms）
辗转相减法（升级版，耗时2ms，引入乘法，提高了相减的效率）

基本步骤如下：

保存符号
对两数取绝对值
辗转相减，记录次数
加上符号，得出结果

基本思想还是用位运算进行/模拟以下运算：求符号；求相反数；求加法/减法（本题可直接使用加法减法，但是升级版代码里我也实现了加法减法）。

辗转相减法（普通版）

//
// Created by jt on 2020/8/14.
//
using namespace std;

class Solution {
public:
    /**
     *
     * @param dividend int整型
     * @param divisor int整型
     * @return int整型
     */
    int divide(int dividend, int divisor) {
        // write code here
        int ans = 0, sign = 0;
        // 1. 保存符号
        if (isPositive(dividend) ^ isPositive(divisor)) sign = 1;
        // 2. 取绝对值
        int x = abs(dividend), y = abs(divisor);
        // 3. 辗转相减
        while (x - y >= 0) {
            x = x - y;
            ans += 1;
        }
        // 4. 加上符号
        if (sign) ans = -ans;
        return ans;
    }

    bool isPositive(int i) {
        return !(i >> 31);
    }

    int abs(int i) {
        if (!isPositive(i)) i = negative(i);
        return i;
    }

    int negative(int i) {
        return ~i + 1;
    }
};

辗转相减法（升级版）

//
// Created by jt on 2020/8/12.
//
using namespace std;

class Solution {
public:
    /**
     *
     * @param dividend int整型
     * @param divisor int整型
     * @return int整型
     */
    int divide(int dividend, int divisor) {
        // write code here
        // 1. 保存符号
        bool isPos = true;
        if (isPositive(dividend) ^ isPositive(divisor)) isPos = false;
        // 2. 取绝对值
        int x = abs(dividend), y = abs(divisor);
        // 3. 辗转相减
        int ans = 0, i = 31;
        while (i >= 0) {
            // 如果够减(即y*(2^i) <= x)
            if ((x >> i) >= y) {
                x = minus(x, y << i);
                ans = plus(ans, 1 << i);
            }
            i = minus(i, 1);
        }
        // 4. 加上符号
        if (!isPos) ans = negative(ans);
        return ans;
    }

    int plus(int i, int j) {
        return j == 0 ? i : plus(i ^ j, (i & j) << 1);
    }

    int minus(int i, int j) {
        return plus(i, negative(j));
    }

    bool isPositive(int i) {
        return !(i >> 31);
    }

    int abs(int i) {
        if (!isPositive(i)) i = negative(i);
        return i;
    }

    int negative(int i) {
        return plus(~i, 1);
    }
};

编辑于 2020-08-14 02:32:28 回复(0)

Aiky

去网上找了一下二进制加减乘除的模板，可以直接用哦

#define LL long long
     LL add(LL num1, LL num2){
        LL sum = num1 ^ num2;
        LL carry = (num1 & num2) << 1;  
        while(carry != 0){
            LL a = sum;
            LL b = carry;
            sum = a ^ b;
            carry = (a & b) << 1;  
        }
        return sum;
    }
    LL substract(LL num1, LL num2){
        LL subtractor = add(~num2, 1);// 先求减数的补码（取反加一）
        LL result = add(num1, subtractor); // add()即上述加法运算　　
        return result ;
    }
    int divide(int a,int b) {   
        // 先取被除数和除数的绝对值    
        LL dividend = a >= 0 ? a : add(~a, 1);    
        LL divisor = b >= 0 ? b : add(~b, 1);    
        LL quotient = 0;// 商    
        LL remainder = 0;// 余数    
        for(int i = 31; i >= 0; i--) {
            //比较dividend是否大于divisor的(1<<i)次方，不要将dividend与(divisor<<i)比较，而是用(dividend>>i)与divisor比较，
            //效果一样，但是可以避免因(divisor<<i)操作可能导致的溢出，如果溢出则会可能dividend本身小于divisor，但是溢出导致dividend大于divisor       
            if((dividend >> i) >= divisor) {            
                quotient = add(quotient, 1 << i);            
                dividend = substract(dividend, divisor << i);        
            }    
        }    
        // 确定商的符号    
        if((a ^ b) < 0){
            // 如果除数和被除数异号，则商为负数        
            quotient = add(~quotient, 1);    
        }    
        // 确定余数符号    
        remainder = b > 0 ? dividend : add(~dividend, 1);    
        return quotient;// 返回商
    }

发表于 2020-03-18 16:11:17 回复(0)

两数相除

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题