今天是紀錄LeetCode解題的第二十九天

第二十九題題目：Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 2^31 - 1, and if the quotient is strictly less than -2^31, then return -2^31.

給定兩個整數 dividend（被除數）與 divisor（除數），在不使用乘法、除法和取餘數運算（*、/、%）的情況下，請實作兩數相除，整數除法的結果必須向零截斷（truncate toward zero），也就是捨去小數部分：
例如 8.345 → 8、 -2.7335 → -2，請回傳這次相除後的「商」，如果結果大於2^31-1回傳2^31-1，如果小於-2^31則回傳-2^31

解題思路

整數除法可以理解為我們要找到一個最大整數q使得divisor * q <= dividend(例如divisor = 3，dividend = 10，而這個最大整數q為3，所以答案就是q=3)，然後用位移的方式來做乘法，把divisor左移i位元(寫作divisor << i)，等價於divisor * 2^i，如果divisor * 2^i <= dividend，代表divisor * 2^i可以從dividend裡減掉，減掉後我們要的商則增加1 << i(因為我們減掉了divisor * 2^i，相當於q加上2^i)

程式碼

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == 0:
            return dividend
        isminus = (dividend < 0) != (divisor < 0) #先判斷答案是否為正負數
        if dividend < 0:dividend = -dividend #一律以正數做計算
        if divisor < 0:divisor = -divisor
        result = 0
        for i in range(31,-1,-1):
            if (divisor << i) <= dividend:
                dividend -= divisor << i
                result += 1 << i
        if isminus:
            result = -result
        return min(max(-2**31,result),2**31-1)

執行過程

初始狀態

• dividend = 10
• divisor = 3
• result = 0
• isminus = 1

跳過前面從i = 2開始

• divisor << 2 = divisor * 2^2 = 3 * 4 = 12 > 10 → 不行減

i = 1

• divisor << 1 = divisor * 2^1 = 3 * 2 = 6 < 10 → True
• dividend = 10 - 6 = 4
• result = 0 + 1 << i = 1 * 2^1 = 2

i = 0

• divisor << 0 = divisor * 2^0 = 3 * 1 = 3 < 4 → True
• dividend = 4 - 3 = 1
• result = 2 + 1 << i = 2 + 1 * 2^0 = 3

最後回傳result = 3即是答案