​LeetCode刷题实战29：两数相除

今天和大家聊的问题叫做 两数相除，我们先来看题面：

https://leetcode-cn.com/problems/divide-two-integers/

给定两个整数，被除数和除数，要求在不使用除法的情况下计算出两数的商

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.

样例 1:

Input: dividend = 10, divisor = 3
Output: 3

样例 2:

Input: dividend = 7, divisor = -3
Output: -2

注意:

• 除数和被除数都在32位int的范围内

• 除数不为0

• 对于超界的情况返回

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−,   − 1]. For the purpose of this problem, assume that your function returns  − 1 when the division result overflows.

题解

暴力

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 判断是否同号
        flag = (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0)
        ret = 0
        # 全部赋值为正
        dividend, divisor = abs(dividend), abs(divisor)
        
        start = 0
        # 模拟除法
        while start + divisor <= dividend:
            start += divisor
            ret += 1
            
        # 防止越界，注意只有正数才有可能越界
        return min(ret, (1 << 31) - 1) if flag else -ret

二进制优化

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 前面处理和之前一样
        flag = (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0)
        ret = 0
        dividend, divisor = abs(dividend), abs(divisor)
        
        # 预处理二进制数组
        binary = [0 for _ in range(33)]
        # 第0位即2的零次方乘上除数，所以就是除数本身
        binary[0] = divisor
        for i in range(1, 33):
            # 后面每一位是前面一位的两倍，因为二进制
            # << 是位运算左移操作，等价于*2，但是速度更快
            binary[i] = binary[i-1] << 1
            
        for i in range(32, -1, -1):
            if binary[i] <= dividend:
                dividend -= binary[i]
                # 答案加上2^i
                ret += (1 << i)
        return min(ret, (1 << 31) - 1) if flag else -ret