LeetCode 29. Divide Two Integers [Medium] [C++] 解題筆記

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.

EX:

        Input: dividend = 7, divisor = -3

        Output: -2

        Explanation: 7/-3 = truncate(-2.33333..) = -2.

想法:

        這題要求不能使用乘法，除法和 mod 運算，因此我們可以使用 "bitwise operation" 來實作，

每次將 除數 left shift 一位就等同於 將除數*2，所以可以透過這個方式搭配加減法來達到除法的效果。

完整程式碼:

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == INT_MIN && divisor == -1) { return INT_MAX; }
        // since divisor will never be 0 by assumption
        //if (divisor == 0)
        int sign = 1;
        if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) { sign = -1; }
        if (divisor == 1) { return dividend; }
        long m = labs(dividend);
        long n = labs(divisor);
        long  q = 0;
        
        while (m >= n) {
            long t = n;
            long p = 1;
            while (m >= (t << 1)) {
                t <<= 1;
                p <<= 1;
            }
            m -= t;
            q += p;
        }
        
        return (sign == 1)? q : q*sign;
    }
};