leetcode_位运算190.颠倒二进制位

190. 颠倒二进制位 颠倒给定的 32 位无符号整数的二进制位。 1. 字符串 class Solution: # @param n, an integer # @return an integer def reverseBits(self, n): res = "" # 创建一个保存结果的空字符串 for b in str(bin(n))[2:]: # 遍历n的二进制数 res = b + res # 把每一位从头部插入res while len(res) < 32: res += "0" return int(res, 2)

执行过程：

假设输入 n = 43261596（即二进制为00000010100101000001111010011100），反转过程如下：

二进制字符串：bin(43261596) 得到 ‘0b10100101000001111010011100’，去掉 ‘0b’ 后得到 ‘10100101000001111010011100’

反转字符串：遍历每一位，将其按顺序添加到 r 前面：

r = ‘0’ r = ‘00’ r = ‘000’ r = ‘0000’ （继续添加，直到所有位反转） 最终得到r = ‘00111001011110000010100101000000’

确保长度为 32 位：反转后的 r 已经是 32 位，所以无需额外填充0

返回结果：将 r = ‘00111001011110000010100101000000’ 转换为整数，得到 964176192

时间复杂度: O(n)

空间复杂度: O(1)

2. 循环 class Solution: # @param n, an integer # @return an integer def reverseBits(self, n): result = 0 for i in range(32): result <<= 1 # 左移 result 为 1 位 result |= (n & 1) # 将 n 的最低有效位加到 result 中 n >>= 1 # n 右移 1 位 return result 执行过程：

第1 步（i = 0）： num = 43261596 = 00000010100101000001111010011100 提取最低有效位：num & 1 = 0（最低位是 0） result = result << 1 = 0 << 1 = 0（将 result 左移一位，为下一位腾出空间） result |= 0 → result = 0（将提取的位加到 result 中） num >>= 1 → num = 21630798（右移 num，去掉最低位）

第 2 步（i = 1）： num = 21630798 = 0000001010010100000111101001110 提取最低有效位：num & 1 = 0（最低位是 0） result = result << 1 = 0 << 1 = 0 result |= 0 → result = 0 num >>= 1 → num = 10815399

第 3 步（i = 2）： num = 10815399 = 000000101001010000011110100111 提取最低有效位：num & 1 = 1（最低位是 1） result = result << 1 = 0 << 1 = 0 result |= 1 → result = 1（将提取的 1 加到 result 中） num >>= 1 → num = 5407699

第 4 步（i = 3）： num = 5407699 = 00000010100101000001111010011 提取最低有效位：num & 1 = 1（最低位是 1） result = result << 1 = 1 << 1 = 2 result |= 1 → result = 3 num >>= 1 → num = 2703849

第 5 步（i = 4）： num = 2703849 = 0000001010010100000111101001 提取最低有效位：num & 1 = 1（最低位是 1） result = result << 1 = 3 << 1 = 6 result |= 1 → result = 7 num >>= 1 → num = 1351924

第 6 步（i = 5）： num = 1351924 = 000000101001010000011110100 提取最低有效位：num & 1 = 0（最低位是 0） result = result << 1 = 7 << 1 = 14 result |= 0 → result = 14 num >>= 1 → num = 675962 …（继续这个过程直到处理完所有 32 位）

直到第 32 步： 经过 32 次循环，num 会变成 0，result 存储了反转后的二进制值

时间复杂度: O(32) = O(1)空间复杂度: O(1)