1. 首页

LeetCode 190. 颠倒二进制位

题目描述

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

 

示例 1:

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

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

提示:

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

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

难度:Middle

前置知识

  • 双指针

公司

  • 阿里
  • 腾讯
  • 百度
  • 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:

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
 * @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);
    }
};

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 190. 颠倒二进制位

链接:https://www.javascriptc.com/4537.html

« 滴滴出行小程序I18n最佳实践
LeetCode 189. 旋转数组»
Flutter 中文教程资源

相关推荐

QR code