題目:

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 2^31 - 1, then return 2^31 - 1, and if the quotient is strictly less than -2^31, then return -2^31.

給定除數和被除數(皆為整數),算出兩者相除的商後回傳
若結果超出[−2^31, 2^31 − 1],則改回傳邊界
限制:不能使用乘除及mod

看到這題我想:不能用乘除算兩數相除,到底要怎麼做啊?
想了好久都沒有頭緒,最後還是翻了討論區
答案揭曉,原來要用位元運算來做
感覺我需要找時間更熟悉位元運算了
雖然我知道該怎麼用,卻不知道什麼時候該用
已經好幾題我翻討論區才知道還有位元運算的作法了

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        
        positive=(dividend < 0) is (divisor < 0)
        dividend,divisor =abs(dividend),abs(divisor)
        res=0
        while dividend >= divisor:
            temp,i=divisor, 1
            while dividend>=temp:
                dividend=dividend-temp
                res=res+i
                i=i<<1
                temp=temp<<1
        if not positive:
            res = -res
        return min(max(-2147483648, res), 2147483647)

有個土法煉鋼的方法可以用加減法來算除法
將被除數不斷減掉除數,直到被除數小於除數
而減幾次就是商,剩下的數就是餘數
但這樣做很慢,所以我們需要位元運算來加速流程

減掉的過程我們當然想要加大減去的數加快速度
像是減掉兩倍的除數,但我們不被允許使用乘法
所以我們求助於位元運算的<<,此操作相當於將一數乘於2
知道基本概念後,就能開始實作了

先判斷商會是正的還是負的,儲存起來
接著被除數和除數取絕對值(上述方法只適用兩者同號)
用res存商,temp預設為除數,i預設為1(代表現在減去的是除數的一倍)
在被除數大於temp時,被除數變為被除數-temp,而res則加上i
之後temp和i都<< 1,不斷重複

當然上面跑到跳出迴圈,被除數有可能依然大於除數
所以外面要再加個迴圈,直到被除數小於除數為止
都要不斷執行上述的迴圈

若事先紀錄商會是負數,res要變為-res
接著判斷res是否超出[−2^31, 2^31 − 1]的範圍
若小於−2^31回傳−2^31,若大於2^31 − 1回傳2^31 − 1
在範圍內回傳res即可
最後執行時間35ms(faster than 91.78%)

那我們下題見