跳至主要內容

0190. 颠倒二进制位

ITCharge大约 1 分钟

0190. 颠倒二进制位open in new window

  • 标签:位运算、分治
  • 难度:简单

题目链接

题目大意

描述:给定一个 3232 位无符号整数 nn

要求:将 nn 所有二进位进行翻转,并返回翻转后的整数。

说明

  • 输入是一个长度为 3232 的二进制字符串。

示例

  • 示例 1:
输入:n = 00000010100101000001111010011100
输出:964176192 (00111001011110000010100101000000)
解释:输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596,
     因此返回 964176192,其二进制表示形式为 00111001011110000010100101000000
  • 示例 2:
输入:n = 11111111111111111111111111111101
输出:3221225471 (10111111111111111111111111111111)
解释:输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293,
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111

解题思路

思路 1:逐位翻转

  1. 用一个变量 resres 存储翻转后的结果。
  2. nn 不断进行右移(即 n >> 1),从低位到高位进行枚举,此时 nn 的最低位就是我们枚举的二进位。
  3. 同时 resres 不断左移(即 res << 1),并将当前枚举的二进位翻转后的结果(即 n & 1)拼接到 resres 的末尾(即 (res << 1) | (n & 1))。

思路 1:代码

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(logn)O(\log n)
  • 空间复杂度O(1)O(1)