在做了 leetcode190. 颠倒二进制位后，对位移操作有了一些新的体会，记录下来形成此文

1. 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位
如输入00000010100101000001111010011100（int为43261596），返回00111001011110000010100101000000（int为964176192）

从数学角度看，这个问题解决起来很容易

• 循环利用模2运算，从右到左地获得输入的每个二进制digit
• 每个二进制digit乘以相应的base(2^k)，然后将乘积加入到结果中

class Solution:
    def reverseBits(self, n: int) -> int:
        base = pow(2, 31)
        res = 0
        while n != 0:
            m = n % 2
            res += base * m
            base = base // 2

            n = n // 2
        return res

从位运算角度看，这个问题解决起来又更加直接了。下面先看一下位移操作

2.计算机的位移操作

数字在计算机中以二进制形式存储，例如0101表示十进制数字5。对5进行乘除法，在计算机的底层实际上是对0101进行了位移。

先看简单的例子：

• 5 * 2 -> 0101左移一位，变为1010，十进制10
• 5 // 2 -> 0101右移一位，变为0010，十进制2

在计算机的世界中，左移一位表示乘以2，右移一位表示除以2（整除）

2.1 复杂整数乘法

那复杂一点，如果要实现5 * 3呢？其实也挺简单的，关键词就是基于二进制形式进行因式分解。5 * 3 = 5 * (2+1) ，即把乘数3分解为2的幂的和形式，其实就是按3的二进制0011形式对3进行拆分——3 = 2^1 + 2^0。这样5 * 3 = 5 * 2 + 5 * 1，那么5 * 2和5 * 1都分别可以通过对0101左移1位和左移0位实现，得到1010和0101，将这两个位移后的值相加就得到1111（十进制15）

2.2 复杂整数除法（这里只讨论整除）

除法是乘法的逆运算，因此在计算机中也可以通过除数的左移不断逼近被除数实现。
如 10/3 = 3 = (2^1 + 2^0), 也就是10 = 3 * 2^1 + 3 * 2^0，将要求的商看成2的i次方的和形式，这时整个除法运算过程如下：

• 1. 倍增除数3来逼近被除数10，得到i=2，此时被除数变为10 - 3 * 2 = 4
• 2. 倍增除数3来逼近被除数4，得到i=1，此时被除数变为4 - 3 * 1 = 1
• 3. 被除数1小于除数3，return。商等于2^1 + 2^0=3

leetcode 29. 两数相除正是要实现32位有符号整数的整除法，可行的代码如下：

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:     
        # 1.通过异或操作（相同为0相异为1），判断dividend 和 divisor 是否同号
        flag = -1 if (dividend ^ divisor) < 0 else 1
        
        # 2.去掉被除数和除数的符号，问题转换为无符号数相除
        dividend = abs(dividend)
        divisor = abs(divisor)

        res = 0
        # 3.除数通过位移来做乘法逼近被除数，进而实现无符号数相除
        while dividend >= divisor:
            temp = 1
            div = divisor
            # 除数不断左移逼近被除数
            while div < dividend:
                div = div << 1
                temp = temp << 1
            if div > dividend:
                div = div >> 1
                temp = temp >> 1
            res += temp
            dividend = dividend - div 
        
        return min(res, (1 << 31) - 1) if flag > 0 else -res

总结一下，不管是乘法还是除法，都可以通过【移位+累加】实现

3.回到leetcode190

那么从位运算的角度看，我们可以将数学角度的代码进行改写，如下：

class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        for i in range(32):
            # res左移一位，在最右侧空出一个【空bit】
            res = res << 1
            # 取当前n最后一位上的数，不是0就是1
            add = n & 1
            # add填充在res的最右侧【空bit】
            res += add
            n = n >> 1
        return res