楔子
大家好，我是张桃狮。
最近我看了B站视频——【【人工智能】冒泡排序算法，3分钟彻底搞懂算法可视化！草履虫都能听懂的冒泡排序，要是还听不懂，我就退出AI圈！（附全套AI资料）】
https://www.bilibili.com/video/BV134iMBeEZs/
视频中up主把冒泡算法的计算过程做成了很棒的动画。
我不清楚up主是用什么软件制作的动画，我打算用自己最熟悉的影刀RPA和Excel表格做一个类似的。
先回顾下什么是冒泡算法。
冒泡排序（Bubble Sort）是一种简单直观的交换类排序算法，其核心思想是：重复地走访过要排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。
这个算法的名字由来很形象：每一轮遍历都会将当前未排序部分中最大（或最小）的元素逐步 “浮” 到数列的末尾，就像水中的气泡向上浮动一样，因此得名冒泡排序。
参考代码是豆包给出的，大家一看就明白。
def bubble_sort(arr): # 复制输入数组，避免修改原数组（可选优化，提升代码健壮性） arr_copy = arr.copy() n = len(arr_copy) # 外层循环：控制排序的轮次，最多需要n-1轮（每轮确定一个最大元素） for i in range(n - 1): # 内层循环：遍历未排序部分，进行相邻元素比较交换 # 每完成一轮，未排序部分长度减少i（末尾i个元素已有序） for j in range(n - 1 - i): # 升序排序：前一个元素大于后一个，交换位置 if arr_copy[j] > arr_copy[j + 1]: arr_copy[j], arr_copy[j + 1] = arr_copy[j + 1], arr_copy[j] return arr_copy# 测试示例test_arr = [64, 34, 25, 12, 22, 11, 90]sorted_arr = bubble_sort(test_arr)print("原始数组：", test_arr)print("排序后数组：", sorted_arr)
我的思路是先用影刀生成一个随机列表。
将列表写入Excel表格。
用冒泡算法对列表进行排序。
相邻元素每次交换都会被重新写入Excel表格。
为了产生动画效果，我需要将Excel表格数据图形化。
我打算通过Excel表格的条件格式-数据条或者色阶来实现。
用到的影刀RPA指令如图。
条件格式-数据条动画效果如下。
条件格式-色阶动画效果如下。
与python代码不同的是，影刀的for次数循环是包含结束数的。
所以python代码中的列表长度-1，在影刀中要改为列表长度-2。
为了能看清楚动画，我在每次写入Excel表格后，增加了0.1秒等待时间。
在影刀中交换两个变量的值需要用到临时变量，还是python方便啊。
闲话讲完，咱们继续力扣刷题。
力扣190. 颠倒二进制位
颠倒给定的 32 位有符号整数的二进制位。示例 1：输入：n = 43261596输出：964176192解释：整数 二进制43261596 00000010100101000001111010011100964176192 00111001011110000010100101000000示例 2：输入：n = 2147483644输出：1073741822解释：整数 二进制2147483644 011111111111111111111111111111001073741822 00111111111111111111111111111110提示：0 <= n <= 231 - 2n 为偶数进阶: 如果多次调用这个函数，你将如何优化你的算法？
我的思路
我知道python有二进制转换函数，但是我打算先自己手搓。
先用n除以2取余数，将n从十进制转为二进制数。
不足32位的在二进制数前面补零。
因为n为偶数，二进制数的尾数肯定是0，颠倒后的二进制数不用考虑负数问题。
将二进制数转为十进制数。
class Solution: def reverseBits(self, n: int) -> int: 二进制文本="" while n>0: 二进制文本=str(n%2)+二进制文本 n=int(n/2) 需要补零的数量=32-len(二进制文本) 二进制文本="0"*需要补零的数量+二进制文本 res=0 m=31 for i in 二进制文本[::-1]: res += int(i)*(2**m) m -= 1 return res
力扣提交通过。
把手搓都改成python内置函数。
class Solution: def reverseBits(self, n: int) -> int: n=bin(n)[2:].zfill(32) n=int(str(n)[::-1],2) return n
代码看起来简洁了很多。
力扣提交通过。
力扣官方题解
方法一：逐位颠倒
力扣的官方代码没有python题解，我把C++的题解发给豆包，让豆包转为python代码，并增加了详细的注释。
class Solution: def reverseBits(self, n: int) -> int: # 1. 初始化反转结果变量rev，初始值为0（对应C++的uint32_t rev = 0） # 用于存储逐位反转后的32位无符号整数结果 rev = 0 # 2. 循环32次（对应32位整数），同时保留原C++代码的n>0判断（可提前终止无效循环，优化效率） # i：循环计数器，标记当前处理的是第i位（从0开始，对应从最低位到最高位） for i in range(32): # 提前终止条件：如果n已经变为0，后续位都是0，反转后仍为0，无需继续循环 if n <= 0: break # 3. 提取n的最低位（对应C++的n & 1） # n & 1：按位与运算，只有n的最低位为1时结果为1，否则为0，精准提取最低位 lowest_bit = n & 1 # 4. 将提取的最低位移到反转后的对应高位（对应C++的(n & 1) << (31 - i)） # 31 - i：原数的第i位（从低到高），反转后应位于第31 - i位（从高到低） # 例如：原数最低位（i=0），反转后应位于最高位（31-0=31位） shifted_bit = lowest_bit << (31 - i) # 5. 将移位后的位合并到结果rev中（对应C++的rev |= ...） # 按位或运算：保留rev中已有的有效位，同时将新的移位后的位写入对应位置 rev |= shifted_bit # 6. n右移1位，丢弃已处理的最低位，准备处理下一位（对应C++的n >>= 1） # 这里使用无符号右移效果等价（Python中>>对于正数是算术右移，与无符号右移一致） n >>= 1 # 7. 关键：保证返回结果是32位无符号整数（模拟C++的uint32_t返回值） # & 0xFFFFFFFF：将结果限制在32位无符号整数范围内，避免Python整数的无限精度带来的干扰 return rev & 0xFFFFFFFF
力扣提交通过。
我就知道这道题没那么简单，原来用了位运算。
位运算中的按位与&和按位或|，在这个代码中频繁使用，所以一定要明白他们的用法。
我的理解是，按位与和按位或分别代表了两种电路逻辑——串联和并联。
把两个开关串联在一起，就是按位与。
把两个开关并联在一起，就是按位或。
注意这里的位运算优先级是，先计算左移右移，然后是按位与，最后是按位或。
如果要调整计算优先级，需要加小括号，小括号里的位运算优先级最高。
返回结果中的0xFFFFFFFF是16进制的最大值，在这道题中其实加不加都行。
之所以用16进制，是因为二进制太长了。
0xFFFFFFFF转为二进制就是0b11111111111111111111111111111111。
也可以写成0b1111_1111_1111_1111_1111_1111_1111_1111。
方法二：位运算分治
同样是用豆包转的python代码。
class Solution: # 定义类常量，对应C++中的私有常量掩码（与原代码完全一致） # 掩码作用：按固定间隔提取二进制位，用于分治交换 M1 = 0x55555555 # 01010101 01010101 01010101 01010101 M2 = 0x33333333 # 00110011 00110011 00110011 00110011 M4 = 0x0f0f0f0f # 00001111 00001111 00001111 00001111 M8 = 0x00ff00ff # 00000000 11111111 00000000 11111111 def reverseBits(self, n: int) -> int: # 第一步：交换相邻的1个比特位 n = (n >> 1) & self.M1 | (n & self.M1) << 1 # 第二步：交换相邻的2个比特位 n = (n >> 2) & self.M2 | (n & self.M2) << 2 # 第三步：交换相邻的4个比特位 n = (n >> 4) & self.M4 | (n & self.M4) << 4 # 第四步：交换相邻的8个比特位 n = (n >> 8) & self.M8 | (n & self.M8) << 8 # 第五步：交换高低16个比特位，完成32位整体反转 n = (n >> 16) | (n << 16) # 关键：限制结果为32位无符号整数，模拟C++的uint32_t返回值 return n & 0xFFFFFFFF
方法一虽然用了位运算，但是还可以进一步优化。
循环处理尾数并左移，需要32次计算。
方法二用了二分法，只需要5次计算就可以搞定。
我忽然想到排序算法是不是也可以用二分法，我听说Python自带的排序函数好像就用了类似方法，有时间可以研究一下。
注意这里的& 0xFFFFFFFF不能省略，因为代码中的最后一个位运算会导致n超过32位。
为了学习位运算，我打算参考这个代码，写一个4位二进制数的颠倒函数。
方法一
class Solution: M1 = 0b0101 def reverseBits(self, n: int) -> int: n = (n >> 1) & self.M1 | (n & self.M1) << 1 n = (n >> 2) | (n << 2) return n & 0b1111n=6solution=Solution()print(solution.reverseBits(n))
打印结果还是6，测试通过。
6的二进制是0110，颠倒过来还是0110。
方法二
class Solution: M1 = 0b0101 M2 = 0b0011 def reverseBits(self, n: int) -> int: n = (n >> 1) & self.M1 | (n & self.M1) << 1 n = (n >> 2) & self.M2 | (n & self.M2) << 2 return nn=6solution=Solution()print(solution.reverseBits(n))
打印结果还是6，测试通过。
学习位运算就是为了告诉我们，不管输入的数字是十进制、八进制还是十六进制，CPU都会转化为二进制做位运算，最后输出的结果会默认从二进制转化为十进制。
位运算是通过硬件逻辑电路实现的，熟练掌握位运算不但可以优化算法，还可以更加了解计算机的底层原理。
后记
我曾经在Excel中做过一个贪吃蛇小游戏。
感兴趣的朋友可以翻看一下前几期的公众号内容，我懒得贴链接了。
当时我想用deque代替列表存放贪吃蛇的身体节点，结果发现影刀不支持deque只好作罢。
我忽然想起列表中的每个节点其实可以用元组来实现。
这些节点用来存放贪吃蛇的身体坐标，每个节点的行号和列号是不变的。
用列表来存放每个节点的坐标值着实有点浪费内存了。
修改起来也非常简单，我只需要将存放坐标值的中括号修改为小括号就完事了。
影刀测试通过。
我是个编程爱好者，小白级别的，如果你跟我一样希望通过力扣刷题，学习各种奇妙的算法，可以关注我，大家一起学习。
