题目大意
#
描述：给定一个 $32$ 位无符号整数 $n$。
要求：将 $n$ 所有二进位进行翻转，并返回翻转后的整数。
说明：
示例：
1
2
3
4
|
输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
|
1
2
3
4
|
输入：n = 11111111111111111111111111111101
输出：3221225471 (10111111111111111111111111111111)
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111。
|
解题思路
#
思路 1：逐位翻转
#
- 用一个变量 $res$ 存储翻转后的结果。
- 将 $n$ 不断进行右移（即
n >> 1），从低位到高位进行枚举，此时 $n$ 的最低位就是我们枚举的二进位。
- 同时 $res$ 不断左移（即
res << 1），并将当前枚举的二进位翻转后的结果（即 n & 1）拼接到 $res$ 的末尾（即 (res << 1) | (n & 1)）。
思路 1：代码
#
1
2
3
4
5
6
7
|
class Solution:
def reverseBits(self, n: int) -> int:
res = 0
for i in range(32):
res = (res << 1) | (n & 1)
n >>= 1
return res
|
思路 1：复杂度分析
#
- 时间复杂度：$O(\log n)$。
- 空间复杂度：$O(1)$。