【每日一题】29. Divide Two Integers

题目描述

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.

Example 2:

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.

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

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

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

提示显示：

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

题解

由于不能使用乘法、除法和取余运算，所以想到利用位运算。位运算可以实现乘法的作用，位运算结合减法可以实现除法和取余效果。

• 首先，考虑corner case：当被除数为INT_MIN，除数为-1时，此时相除会导致数据溢出，所以直接返回INT_MAX；题目中提示被除数不为0，当然也可以考虑；
• 其他情况，使用位运算：假设a是被除数，b是除数，c是余数，d是商，我们可以知道a = b * d + c,其中，商d可以分解为2的若干次幂的和，余数c 小于被除数b，在这个前提下，我们在a的基础上，反复减去b，同时记录b被减地次数，当a<b时，结束循环。
  • 其中，反复减的过程，我们可以用位运算加快效率；
  • 同时，运算过程中可能会出现数据越界，(为了保证数据不溢出，这里将int转为long进行存储----其实违规了，就当是为了学习位运算的用法吧)

完整代码：

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (divisor == 0 || (dividend == INT_MIN && divisor == -1))
            return INT_MAX;
        # 异或操作，用于判断两者是否同号
        int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;
        
        long m = labs(dividend), n = labs(divisor), res = 0;
        
        while (m >= n){
            long p = n, t = 1;
            
            while (m >= (p << 1)){
                p <<= 1;
                t <<= 1;
            }
            res += t;
            m -= p;
        }
        
        return sign * res;
    }
};

违规方法：但是能OC

• 首先，处理Corner case；
• 正常情况，将dividend 和divisor转换成long型，然后做除法，最后转化成int进行输出

代码：

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (divisor == 0 || (dividend == INT_MIN && divisor == -1))
            return INT_MAX;

        return int(long(dividend)/long(divisor));
    }
};

reference

https://www.cnblogs.com/grandyang/p/4431949.html