# LeetCode: 29.两数相除¶

## 1、题目描述¶

输入: dividend = 10, divisor = 3



输入: dividend = 7, divisor = -3



• 被除数和除数均为 32 位有符号整数。
• 除数不为 0。
• 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

## 2、解题思路¶

​ 首先，如果当前数大于除数，我们就循环判断，为了加快进度，使用移位操作，如果大于其二倍，被除数左移一位，每一次左移一位，直到大于除数停止，这时候，我们减去这个值，然后继续判断，直到最后

class Solution:
def divide(self, dividend, divisor):
"""
:type dividend: int
:type divisor: int
:rtype: int
"""
num1 = abs(dividend)
num2 = abs(divisor)

res = 0

while num1 >= num2:
temp = num2
count = 1
while (temp << 1) < num1:
temp = temp << 1
count = count << 1
res += count
num1 -= temp
if (dividend > 0) ^ (divisor > 0):
return -res
if res >= 2 ** 31:
return 2 ** 31-1
return res


class Solution(object):
def divide(self, dividend, divisor):
"""
:type dividend: int
:type divisor: int
:rtype: int
"""
if dividend == ~(1 << 31) + 1 and divisor == -1:
return (1 << 31) - 1

if divisor == ~(1 << 31) + 1:
if dividend == ~(1 << 31) + 1:
return 1
else:
return 0

sign = (dividend > 0) ^ (divisor > 0)

nums = 0
temp_num = 0

temp_dividend = dividend
pre_divisor = ~divisor + 1 if divisor < 0 else divisor
temp_divisor = pre_divisor
abs_divisor = pre_divisor
if temp_dividend == ~(1 << 31) + 1:
temp_dividend += pre_divisor
nums = 1

temp_dividend = ~temp_dividend + 1 if temp_dividend < 0 else temp_dividend

while temp_dividend >= abs_divisor:
temp_num = 0
temp_divisor = abs(divisor)
for i in range(32):
temp = temp_divisor << i
if temp_dividend >= temp:
temp_num = 1 << i
pre_divisor = temp
else:
nums += temp_num
temp_dividend -= pre_divisor
break
if temp_dividend >= pre_divisor:
nums += temp_num
temp_dividend -= pre_divisor

if sign:
return nums
else:
return (~nums) + 1

class Solution:
def divide(self, dividend: int, divisor: int) -> int:
dvd = dividend
dvs = divisor
nums = 0
sign = not((dividend > 0) ^ (divisor > 0))

if dvs == ~(1 << 31) + 1:
if dvd == ~(1 << 31) + 1:
return 1
else:
return 0
dvs = ~dvs + 1 if dvs < 0 else dvs

if dvd == ~(1 << 31) + 1:
if divisor == -1:
return (1 << 31) - 1
else:
nums = 1
dvd = ~(dvd + dvs) + 1

dvd = ~dvd + 1 if dvd < 0 else dvd

while dvd >= dvs:
temp = dvs
count = 1
while (temp << 1) < dvd:
temp <<= 1
count <<= 1
nums += count
dvd -= temp

return nums if sign else (~nums) + 1