两数相除

难度: Easy

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

注意：

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2³¹, 2³¹−1]。本题中，如果除法结果溢出，则返回 2³¹− 1

示例 1：

输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7

示例 2：

输入：a = 7, b = -3
输出：-2
解释：7/-3 = truncate(-2.33333..) = -2

示例 3：

输入：a = 0, b = 1
输出：0

示例 4：

输入：a = 1, b = 1
输出：1

提示:

-2³¹ <= a, b <= 2³¹ - 1
b != 0

注意：本题与主站 29 题相同：https://leetcode-cn.com/problems/divide-two-integers/

Submission

运行时间: 22 ms

内存: 15.9 MB

class Solution:
    def divide(self, a: int, b: int) -> int:
        if (a>0 and b>0) or (a<0 and b<0) :
            flag = True
        else:
            flag = False
        a=abs(a)
        b=abs(b)
        res = 0
        while a>=b:
            n=1
            t=b
            while a > (t <<1):
                n <<=1
                t<<=1
            a -= t
            res += n
        if flag ==False:
            res = -res
        return res if -2**31 <=res <= 2**31-1 else 2**31 - 1

Explain

此题解采用位操作和减法来实现除法。首先，确定结果的符号（正或负），接着将被除数和除数都转化为绝对值。利用循环和位移操作（左移相当于乘以2），动态地增加除数，使其尽可能接近被除数，同时累积对应的倍数。每次循环结束时，从被除数中减去当前增加的除数，并累加计算得到的商。最后，根据最初确定的符号调整结果。如果结果溢出32位整型范围，则返回最大或最小值。

时间复杂度: O((log(n))^2)

空间复杂度: O(1)

class Solution:
    def divide(self, a: int, b: int) -> int:
        # 确定结果的符号
        if (a > 0 and b > 0) or (a < 0 and b < 0):
            flag = True
        else:
            flag = False
        # 将a和b都取绝对值
        a = abs(a)
        b = abs(b)
        res = 0
        # 主循环：当a大于等于b时执行
        while a >= b:
            n = 1
            t = b
            # 通过位移找到最大的t和n，使得t <= a
            while a > (t << 1):
                n <<= 1
                t <<= 1
            # 从a中减去最大的t，同时累加对应的n到结果中
            a -= t
            res += n
        # 根据符号调整结果
        if not flag:
            res = -res
        # 处理可能的溢出情况
        return res if -2**31 <= res <= 2**31 - 1 else 2**31 - 1

Explore

题解中的表述可能有误导，事实上位移操作是为了快速找到不超过a的最大的t的倍数。在每次循环中，t从除数b开始，通过左移（乘以2）逐步增加，直到t的下一个翻倍会超过a。因此，当找到最大的不超过a的t时，这个t不一定是a的一半，而是在不超过a的范围内最接近a的t的倍数。每次减去这样的t后，a至少减少了原来的b，而不是减少到原来的一半。

在算法中，如果位移后的t值超过了被除数a，位移操作会停止，并退回到最后一次未超过a的t值。随后，这个t值会从a中被减去，相应的倍数n也累加到结果res中。之后，a和t都会重新调整，t重新设置为除数b，n重置为1，再次进行循环和位移操作，直到a小于b为止。

在Python中，整数类型可以自动扩展，因此理论上不会直接溢出。但在其他一些编程语言中，如C++或Java，32位整数的范围是从-2^31到2^31-1。当尝试将-2^31转换为其正数形式时，由于2^31超出了正数的最大范围，会导致溢出。在Python中，虽然不会溢出，但这种情况需要特别注意，因为它可能在其他语言的实现中引发问题。