LeetCode题解190.reverse-bits

题目地址

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.

思路

这道题是给定一个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

拓展

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

  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题解150.evaluate-reverse-polish-notation

题目地址 https://leetcode.com/problems/evaluate-reverse-polish-notation/description/ 题目描述 Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are…

如何告诉Checker遗留方法将接受Nullable类型？ - java

考虑一下：@Nullable Object obj = null; Optional<Object> optional = Optional.ofNullable(obj); 这会失败，因为检查器框架假定ofNullable无法接受null值（毕竟，其参数未标记为@Nullable）。有没有办法告诉Checker-framework这个方法（或我…

Spacy如何将标记标签整体化？ - python

在包含＃标签（例如tweet）的句子中，spacy的令牌生成器将标签分为两个令牌：import spacy nlp = spacy.load('en') doc = nlp(u'This is a #sentence.') [t for t in doc] 输出：[This, is, a, #, sentence, .…

页面加载而不是提交时发生struts验证 - java

请原谅我;我对Struts有点陌生。我遇到一个问题，即页面加载而不是我实际提交表单时发生了验证。我整天都在论坛上搜寻和搜寻，没有任何运气。我显然做错了一些事情，应该很容易确定，但是我还没有发现问题所在。这是我的struts.xml的片段：<action name="*Test" method="{1}" clas…

我收到一个IndentationError。我如何解决它？ - python

我有一个Python脚本：if True: if False: print('foo') print('bar') 但是，当我尝试运行脚本时，Python引发IndentationError： File "script.py", line 4 print('bar') ^ Ind…

推荐标签：,

腾讯的同事天天给我安利让我看《三体》，说马化腾和雷军也在…

腾讯的同事天天给我安利让我看《三体》，说马化腾和雷军也在看。自己强行看了两个月，全部给看完了。感觉这文笔也就我读初中的水平……而且写着国内的一些情况，外国人能理解吗？这书为什么会这么火？这水平我也可以去写呀[笑哭][笑哭][笑哭] 招商银行员工：可以写赶紧写一个啊，能拿科幻文学雨果奖。 包清白：哦 楼主：pei ！tui ！你也配姓龙 楼主：@赵龙王 呵呵 […]