0%

【LeetCode with Python】 29. Divide Two Integers

题目

原题页面:https://leetcode.com/problems/divide-two-integers/
本文地址:</divide-two-integers/>
题目类型:Math, Binary Search
难度评价:Medium

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.


分析


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
# @return an integer
def divide(self, dividend, divisor):

if 0 == divisor or 0 == dividend:
return 0
elif 1 == divisor or -1 == divisor:
return dividend * divisor

positive = 1
if (dividend >0 and divisor < 0) or (dividend < 0 and divisor > 0):
positive = -1
dividend = dividend if dividend > 0 else -dividend
divisor = divisor if divisor > 0 else -divisor

result = 0
dividend_now = dividend
while dividend_now >= divisor:
total = divisor
sub_result = 1
while True:
total = total << 1
sub_result = sub_result << 1 ## not += 2
if total > dividend_now:
total = total >> 1
sub_result = sub_result >> 1
break
elif total == dividend_now:
break
result += sub_result
dividend_now -= total
return result * positive