运算符

符号 意义
& 与，1&1=1，其他情况为0
| 或，0|0=0，其他为1
~ 逐位取反
^ 异或，同0异1
<< 左移
>> 右移

简单来看一下操作吧：

倍乘

1
2
print(5<<1)
# 10

5: 101=1*4+0*2+1*

5<<1: 1010=1*8+0*4+1*2+0*1=2(1*4+0*2+1*1+0*1)=2(101)

倍除

1
2
print(5>>1)
# 2

奇数判断

1
A&1==1?

案例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def coinChange(self, coins, amount: int) -> int:
        if not amount:
            return 0
        # 将减法转换为除法进行运算
        # 一旦最低位为1，则说明找到解，停止运算
        dp = 1 << amount
        res = 0
        while dp:
            tmp = 0
            res += 1
            # 每一轮运算计算一遍dp除以2**i得到的所有可能解
            for coin in coins:
                # tmp用于存储运算的中间结果
                # dp >> coin 实际上是进行除法运算：dp//2**coin
                # 使用位运算“或”来保存全部除法运算结果中的‘1’，实现批量运算
                # ps:这也是二进制移位的一个神奇之处，大家可以手动模拟一下这个过程
                tmp |= dp >> coin
            # 一旦末尾出现1，则返回结果
            if tmp & 1:
                return res
            # 将本轮运算的全部运算结果送入下一轮计算
            dp = tmp
        return -1