两数相除

问题描述

给定两个整数，被除数 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。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/divide-two-integers

思路

• 首先对特殊情况进行判断，当dividend==0，直接return 0；
• 在计算的过程中不考虑符号的问题，要对除数和被除数进行取绝对值，因此要先其转化为long long类型，防止溢出
• 将除数放大count倍，在这个过程中保证lldividend>=lldivisor
• 被除数依次减去被除数的count倍，右移 count 循环执行减法，直到被除数为0 或者 coun = 0；
• 判断符号，得到真实的result
• 如果result超过INT_MAX，则返回INT_MAX，否则返回result。

题解

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend==0) return 0;
        long long lldividend=dividend;
        lldividend=abs(lldividend);
        long long lldivisor=divisor;
        lldivisor=abs(lldivisor);
        long long count=1,result=0;
        while (lldividend>=lldivisor<<1){
            lldivisor<<=1;
            count<<=1;
        }
        while (count>=1&&lldividend>0){
            if(lldividend>=lldivisor){
                lldividend-=lldivisor;
                result+=count;
            }
            lldivisor>>=1;
            count>>=1;
        }
        if(dividend>0&&divisor<0||dividend<0&&divisor>0){
            result=-result;
        }
        if(result>INT_MAX) return INT_MAX;
        else return (int)result;
    }
};