乘除法是我们再熟悉不过的算数计算操作。在我们的认知中，乘法的本质是加法，除法的本质是减法。在计算机中，乘除法的底层实现也正是通过加减操作完成的

乘除法与加减法联系起来是显而易见的，但它与【位移操作】之间存在着更加直观的联系，而这往往被忽略

乘除法与位移操作

位移操作，就是对一个n进制的数按位进行左移或者右移。左移一位，扩大n倍，等于乘以n；右移一位，缩小n倍，等于除以n（指取整的除法）
例如：
十进制数1234，左移一位，得12340，也就是乘以10；右移一位，得123，也就是除以10取整

可以看到，位移只需要进行【非常简单的左右移动操作】，就实现了n倍增/n倍减的效果，比基于反复加减的乘除法更加高效

计算机中的位移操作

在计算机中，都以【二进制方式】存储数字。因此，在计算机中对数字进行位移操作，是在进行乘以2/除以2的操作
以二进制数111（十进制7）为例，左移一位，得到1110（十进制14）；右移一位，得到11（十进制3）

位移操作在程序算法中的应用

• 通常如果需要乘以或除以2的n次方，都可以用移位的方法代替
• 可以用来【分解过大的十进制数字为2的i次方的和形式】，如10 = 2^3 + 2^1

例1
leetcode 50
实现pow(x, n)函数，计算x的n次幂
（也就是通过分解指数n为2的i次方的和形式实现快速幂）

class Solution:
    def myPow(self, x: float, n: int) -> float:
        negative = n < 0

        n = abs(n)
        res = 1
        base = x
        # 核心代码
        while n != 0:
            # 和1进行与运算，判断n的最后一位是否为数字1
            if n & 1 == 1:
                res *= base
            # 右移一位
            n >>= 1
            # 更新base
            base *= base
        return res if not negative else 1/res

例2
leetcode 29 计算两数的商（取整）

# 思路：将被除数和除数取绝对值后，将要求的商看成2的i次方的和形式，从而利用位移操作
# 如10/3 = (2^1 + 2^0), 也就是10 = 3 * 2^1 + 3 * 2^0
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == (-2**31) and divisor == -1:
            return 2**31 - 1
        # 使用异或检查是否同号
        same_sign = (dividend ^ divisor) >= 0
        dividend = abs(dividend)
        divisor = abs(divisor)
        if dividend < divisor:
            return 0
        else:
            # 结果res初始化为0
            res = 0
            divisor_ori = divisor
            while dividend >= divisor:
                # temp初始化为2的0次方
                temp = 1
                while dividend >= divisor<<1:
                    divisor <<= 1
                    temp <<= 1
                dividend -= divisor
                res += temp
                # 因为除数进行了位移，所以要恢复
                divisor = divisor_ori
            return res if same_sign else -1*res