Skip to content

Latest commit

 

History

History
184 lines (136 loc) · 4.5 KB

190.reverse-bits.md

File metadata and controls

184 lines (136 loc) · 4.5 KB
Raw

题目地址(190. 颠倒二进制位)

https://leetcode-cn.com/problems/reverse-bits/

题目描述

颠倒给定的 32 位无符号整数的二进制位。

 

示例 1：

输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
示例 2：

输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
 

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。
 

进阶:
如果多次调用这个函数，你将如何优化你的算法？

前置知识

  • 双指针

公司

  • 阿里
  • 腾讯
  • 百度
  • airbnb
  • apple

思路

这道题是给定一个 32 位的无符号整型，让你按位翻转， 第一位变成最后一位， 第二位变成倒数第二位。。。

那么思路就是双指针

这个指针可以加引号

  • n 从高位开始逐步左， res 从低位（0）开始逐步右移
  • 逐步判断，如果该位是 1，就 res + 1 , 如果是该位是 0， 就 res + 0
  • 32 位全部遍历完，则遍历结束

关键点解析

  1. 可以用任何数字和 1 进行位运算的结果都取决于该数字最后一位的特性简化操作和提高性能

eg :

  • n & 1 === 1, 说明 n 的最后一位是 1
  • n & 1 === 0, 说明 n 的最后一位是 0

  1. 对于 JS，ES 规范在之前很多版本都是没有无符号整形的， 转化为无符号，可以用一个 trickn >>> 0

  2. 双"指针" 模型

  3. bit 运算

代码

  • 语言支持：JS，C++，Python，Java

JavaScript Code：

/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function (n) {
  let res = 0;
  for (let i = 0; i < 32; i++) {
    res = (res << 1) + (n & 1);
    n = n >>> 1;
  }

  return res >>> 0;
};

C++ Code：

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        auto ret = 0;
        for (auto i = 0; i < 32; ++i) {
            ret = (ret << 1) + (n & 1);
            n >>= 1;
        }
        return ret;
    }
};

Python Code:

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        result = 0
        for i in range(32):
            result = (result << 1) | (n & 1)
            n >>= 1
        return result
# or
class Solution:
    def reverseBits(self, n: int) -> int:
        ans = 0
        for i in range(31, -1, -1):
            ans |= ((n >> i) & 1) << (31 - i)
        return ans

Java Code：

public class Solution {
    public int reverseBits(int n) {
        int rev = 0;
        for (int i = 0; i < 32 && n != 0; ++i) {
            rev |= (n & 1) << (31 - i);
            n >>>= 1;
        }
        return rev;
    }
}

复杂度分析

  • 时间复杂度：$O(logN)$
  • 空间复杂度：$O(1)$

拓展

不使用迭代也可以完成相同的操作：

  1. 两两相邻的 1 位对调
  2. 两两相邻的 2 位对调
  3. 两两相邻的 4 位对调
  4. 两两相邻的 8 位对调
  5. 两两相邻的 16 位对调

C++代码如下：

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        auto ret = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
        ret = ((ret & 0xcccccccc) >> 2) | ((ret & 0x33333333) << 2);
        ret = ((ret & 0xf0f0f0f0) >> 4) | ((ret & 0x0f0f0f0f) << 4);
        ret = ((ret & 0xff00ff00) >> 8) | ((ret & 0x00ff00ff) << 8);
        return ((ret & 0xffff0000) >> 16) | ((ret & 0x0000ffff) << 16);
    }
};

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。