[LeetCode] 29. 两数相除

[Animenzzzz]

题目描述：

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

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

示例 1:

输入: dividend = 10, divisor = 3
输出: 3

示例 2:

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

说明:

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

解题思路：使用常规无脑的一次次递减，直接超时。。要不然就是easy的标签的。看了网上的思路，学会使用位运算扩大倍数来提高循环的效率。首先除数两倍两倍的增大，结果p也成倍增大，直到增大到大于等于被除数，然后累加p，被除数减小当前增大的除数，除数还原，继续如此循环。这题还要另外特殊处理的是int最大值最小值的问题，特殊值另外判断返回。

C++解题：

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX;
        int fu_flag = 0;
        long long tmp1,tmp2,res = 0;
        if(dividend < 0) fu_flag++;
        if(divisor < 0) fu_flag++;
        tmp1 = abs((long long)dividend);
        tmp2 = abs((long long)divisor);
        if(tmp1 == 0) return 0;
        if(tmp2 == 1) return fu_flag == 1 ? -tmp1:tmp1;
        while (tmp1 >= tmp2)
        {
            long long nn = tmp2,p = 1;
            while (tmp1 >= (nn<<1))
            {
                nn = nn<<1;
                p = p<<1;
            }
            res+=p;
            tmp1 = tmp1 - nn;
        }
        if(fu_flag == 1) return -res;
        return res;
    }
};