leetcode with python:29. Divide Two Integers

题目:

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%)

那我们下题见