Skip to content

Latest commit

 

History

History
211 lines (166 loc) · 5.61 KB

190.reverse-bits.md

File metadata and controls

211 lines (166 loc) · 5.61 KB
Raw

题目地址

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

题目描述

Reverse bits of a given 32 bits unsigned integer.



Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10101111110010110010011101101001.


Note:

Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -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

JavaScript Code：

/*
 * @lc app=leetcode id=190 lang=javascript
 *
 * [190] Reverse Bits
 *
 * https://leetcode.com/problems/reverse-bits/description/
 *
 * algorithms
 * Easy (30.30%)
 * Total Accepted:    173.7K
 * Total Submissions: 568.2K
 * Testcase Example:  '00000010100101000001111010011100'
 *
 * Reverse bits of a given 32 bits unsigned integer.
 *
 *
 *
 * Example 1:
 *
 *
 * Input: 00000010100101000001111010011100
 * Output: 00111001011110000010100101000000
 * Explanation: The input binary string 00000010100101000001111010011100
 * represents the unsigned integer 43261596, so return 964176192 which its
 * binary representation is 00111001011110000010100101000000.
 *
 *
 * Example 2:
 *
 *
 * Input: 11111111111111111111111111111101
 * Output: 10111111111111111111111111111111
 * Explanation: The input binary string 11111111111111111111111111111101
 * represents the unsigned integer 4294967293, so return 3221225471 which its
 * binary representation is 10101111110010110010011101101001.
 *
 *
 *
 * Note:
 *
 *
 * Note that in some languages such as Java, there is no unsigned integer type.
 * In this case, both input and output will be given as signed integer type and
 * should not affect your implementation, as the internal binary representation
 * of the integer is the same whether it is signed or unsigned.
 * In Java, the compiler represents the signed integers using 2's complement
 * notation. Therefore, in Example 2 above the input represents the signed
 * integer -3 and the output represents the signed integer -1073741825.
 *
 *
 *
 *
 * Follow up:
 *
 * If this function is called many times, how would you optimize it?
 *
 */
/**
 * @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

复杂度分析

  • 时间复杂度：$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 。 目前已经35K star啦。

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