Leetcode-29.两数相除

发表于 分类于 阅读次数：

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
示例 2:

输入: dividend = 7, divisor = -3
输出: -2
说明:

被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31,  2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。

解法：位运算

商s=0,信号量sign=(dividend>0)^(divisor>0) 判断s的最终符号

两层循环，第一层循环当 当前被除数Idividend大于除数Idivisor 时，初始增量i=1，中间除数temp初始为除数Idivisor

第二层循环当 当前被除数Idividend大于当前除数temp 时， 当前被除数Idividend-=temp ，s+=i;i左移1位，temp左移1位

一种种特殊情况

  • 当Idividend=INT_MIN Idivisor==-1时 直接返回INT_MAX
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int divide(int dividend, int divisor) {
        long long s=0;
        int sign;
        if(dividend==INT_MIN&&divisor==-1)
            return INT_MAX;
        if(divisor==1)
            return dividend;
        if(divisor==-1)
            return -dividend;
        sign=(dividend>0)^(divisor>0);
        long long Idividend=abs((long long)dividend);
        long long Idivisor=abs((long long)divisor);
        while(Idividend>=Idivisor)
        {
            long long i=1;
            long long temp=Idivisor;
            while(Idividend>=temp)
            {
                Idividend-=temp;
                s+=i;
                i<<=1;
                temp<<=1;
            }
        }
        if(sign==1) s=-s;
        return (int)s;
    }
};