動機
阿,除法
Problem
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
.
Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]
. For this problem, assume that your function returns 231 − 1
when the division result overflows.
Example 1:
Input: dividend = 10, divisor = 3Output: 3Explanation: 10/3 = truncate(3.33333..) = 3.
Example 2:
Input: dividend = 7, divisor = -3Output: -2Explanation: 7/-3 = truncate(-2.33333..) = -2.
Example 3:
Input: dividend = 0, divisor = 1Output: 0
Example 4:
Input: dividend = 1, divisor = 1Output: 1
Constraints:
-231 <= dividend, divisor <= 231 - 1
divisor != 0
Sol
一直把除數乘2,直到比被除數小一點,扣掉,loop
class Solution:
def divide(self, p: int, q: int) -> int:
int_max = (1 << 31)
minus, ret = (p < 0) ^ (q < 0), 0
p,q = abs(p), abs(q)
while p >= q:
tmp,part = q,1
while p >= (tmp << 1): # 從最右邊開始扣
tmp, part = (tmp << 1), (part << 1)
ret, p = ret+part, p-tmp
if minus:
ret = max(-ret, -int_max)
else:
ret = min(ret, int_max-1)
return ret