LeetCode题解：29.两数相除【Python题解超详细，位运算、二分查找法、递归法】，知识拓展：位运算

标签：运算 temp 题解左移除数 dividend 两数 divisor

题目描述

给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。返回被除数 dividend 除以除数 divisor 得到的商。

注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−, −− 1] 。本题中，如果商 严格大于 −− 1 ，则返回 −− 1 ；如果商 严格小于 −，则返回 − 。

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333.. ，向零截断后得到 3 。

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。

提示：

-231 <= dividend, divisor <= 231 - 1
divisor != 0

解答

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        # # 思路一：位运算求商
        # # 定义截断范围，即最大值和最小值
        # INT_MAX=2**31-1
        # INT_MIN=-2**31
        # # 特殊情况dividend=0
        # if dividend==0:
        #     return 0
        # # 确定结果符号
        # sign = -1 if (dividend<0)^(divisor<0)  else 1
        # #将其转化为正数，以便于运算
        # dividend,divisor=abs(dividend),abs(divisor)
        # # 初始化结果
        # result=0
        # # 位运算求商
        # # 外层循环
        # while dividend >= divisor:
        #     temp_divisor, multiple = divisor, 1
        #     # 内层循环
        #     while dividend > (temp_divisor << 1):
        #         # 对两者进行位运算，不断左移
        #         temp_divisor <<= 1
        #         multiple <<=1
        #     dividend-=temp_divisor
        #     result+=multiple
        # # 结果附加符号
        # result=sign*result
        # # 返回结果
        # return max(INT_MIN,min(INT_MAX,result))

        # 思路二：二分查找法       
        # # 定义截断范围，即最大值和最小值
        INT_MAX=2**31-1
        INT_MIN=-2**31
        # 特殊情况dividend=0
        if dividend==0:
            return 0
        # 确定结果符号
        sign = -1 if (dividend<0)^(divisor<0)  else 1
        #将其转化为正数，以便于运算
        dividend,divisor=abs(dividend),abs(divisor)
        # 初始化结果
        result=0
        # 二分查找的左右边界
        left,right=0,dividend
        while left<=right:
            mid=(left+right)//2
            # 根据判定条件，不断移动边界
            if mid*divisor <= dividend:
                result=mid
                left=mid+1
            else:
                right=mid-1
        # 结果附加符号
        result=sign*result
        # 返回结果
        return max(INT_MIN,min(INT_MAX,result))


        # # 思路三：迭代法
        # # 定义截断范围，即最大值和最小值
        # INT_MAX=2**31-1
        # INT_MIN=-2**31
        # # 特殊情况dividend=0
        # if dividend==0:
        #     return 0
        # # 确定结果符号
        # sign = -1 if (dividend<0)^(divisor<0)  else 1
        # #将其转化为正数，以便于运算
        # dividend,divisor=abs(dividend),abs(divisor)
        # # 初始化结果
        # result=0
        # # 迭代
        # def divide_helper(dividend,divisor):
        #     if dividend < divisor:
        #         return 0 
        #     # 外层循环
        #     temp_divisor, multiple = divisor, 1
        #     # 内层循环
        #     while dividend > (temp_divisor << 1):
        #         # 对两者进行位运算，不断左移
        #         temp_divisor <<= 1
        #         multiple <<=1
        #     dividend-=temp_divisor
        #     return multiple+divide_helper(dividend,divisor)
        # result=divide_helper(dividend,divisor)
        # # 结果附加符号
        # result=sign*result
        # # 返回结果
        # return max(INT_MIN,min(INT_MAX,result))

思路一，位运算求商：通过位运算模拟除法。每次在被除数大于等于除数时，倍增当前除数（通过左移操作实现乘 2），同时记录对应的倍数。内层循环结束后，从被除数中减去倍增的最大除数，并将倍数累积到结果中。最终根据符号计算结果，并确保结果在有效范围内。

思路二，二分查找法：利用二分查找在 [0, abs(dividend)] 范围内寻找商。通过比较 mid * divisor 和 dividend 来调整二分的左右边界，逐步逼近最大合法的商值。每次更新结果 result 时，确保当前的 mid 不超过被除数。最终根据符号和范围调整返回结果。

思路三，递归法：递归地通过倍增法计算商。定义一个辅助函数，在每次递归中，通过左移操作寻找当前最大的倍数，然后从被除数中减去当前倍增的除数，递归计算剩余部分的商。最终将所有的倍数累积起来得到结果，再根据符号调整并返回结果，确保在合法范围内。

知识拓展：位运算

相信有同学在看到方法一中的 << 符号时，第一感觉就是编程中还会用到远小于号吗？哈哈，其实它并不是远小于号，而是一种特殊的运算符号，位运算符。位运算可能听起来很“低级”，但它快得飞起！无论是高效算法还是底层优化，它都有一席之地。别怕，今天用轻松的方式让你掌握位运算，用它吊打常规乘除法！

位运算是什么？

位运算，就是直接对数字的 二进制位 进行操作。二进制大家都知道：1010 啦，1101 啦（都是机器语言的心头好）。

你平时的数字：5，-7 在计算机中其实是以二进制形式存储的：

正数：直接翻译成二进制，比如 5 = 101。
负数：用 补码表示（别怕，后面用不到负数位的操作）。

常见位运算符

Python 里的位运算符有如下几个：

运算符	名称	含义	示例
`<<`	左移	把所有二进制位左移 n 位，相当于乘以 $2^n$ 。	`5 << 1 = 10` （`101 -> 1010`）
`>>`	右移	把所有二进制位右移 n 位，相当于整除。	`5 >> 1 = 2` （`101 -> 10`）
`&`	按位与	每个位同时为 1，结果才是 1。	`5 & 3 = 1` （`101 & 011 = 001`）
`	`	按位或	只要有一个位是 1，结果就是 1。
`^`	按位异或	相同为 0，不同为 1。	`5 ^ 3 = 6` （`101 ^ 011 = 110`）
`~`	按位取反	把每个位的 0 和 1 反转（包括符号位）。	`~5 = -6`

重点掌握左移 (`<<`) 和右移 (`>>`)

这两个操作是位运算的灵魂！

左移 (<<)：
- 每左移一位，数值翻倍，后面补零。
- 类似你写数学作业时，在数后面补 0（比如 10 * 10 = 100）。
- 示例：
```
x = 3  # 二进制是 11
print(x << 1)  # 输出 6 (二进制变成 110)
print(x << 2)  # 输出 12 (二进制变成 1100)
```
右移 (>>)：
- 每右移一位，数值整除 2，后面直接砍掉。
- 类似你平时整数除法（只保留商，余数扔掉）。
- 示例：
```
x = 8  # 二进制是 1000
print(x >> 1)  # 输出 4 (二进制变成 100)
print(x >> 2)  # 输出 2 (二进制变成 10)
```

在代码中的应用：倍增法

还记得代码中这段吗？

while dividend >= (temp_divisor << 1):
    temp_divisor <<= 1
    multiple <<= 1

这就是用 左移操作 实现的 倍增法。每次将 temp_divisor 和 multiple 左移一位，相当于把当前除数和倍数都乘以 2。

为什么用左移？
因为直接操作位比用乘法快，而且不引入浮点数，超级高效！
数学对应关系：
如果你原来写：
```
temp_divisor *= 2
multiple *= 2
```
那么用位运算就是：
```
temp_divisor <<= 1
multiple <<= 1
```

总结一下

左移 (<<) = 乘以 2，右移 (>>) = 整除 2。
位运算在效率和 简洁性 上无敌，但一定要注意适用场景（整数和非负数更安全）。
今天用它解除了一个“不能用乘法”的除法题，你是不是觉得位运算简直有点酷？

学会了 << 和 >>，你就掌握了算法题中最常用的位运算技巧！下次再见，一起让代码飞起来～

标签：运算,temp,题解,左移,除数,dividend,两数,divisor
From： https://blog.csdn.net/m0_74420622/article/details/143988348

LeetCode题解：29.两数相除【Python题解超详细，位运算、二分查找法、递归法】，知识拓展：位运算

题目描述

解答

知识拓展：位运算

位运算是什么？

常见位运算符

重点掌握左移 (`<<`) 和右移 (`>>`)

在代码中的应用：倍增法

总结一下

相关文章

赞助商

阅读排行

LeetCode题解：29.两数相除【Python题解超详细，位运算、二分查找法、递归法】，知识拓展：位运算

题目描述

解答

知识拓展：位运算

位运算是什么？

常见位运算符

重点掌握左移 (<<) 和右移 (>>)

在代码中的应用：倍增法

总结一下

相关文章

赞助商

阅读排行

重点掌握左移 (`<<`) 和右移 (`>>`)