题目描述
颠倒给定的 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进行位运算的结果都取决于该数字最后一位的特性简化操作和提高性能
eg :
- n & 1 === 1, 说明n的最后一位是1
- n & 1 === 0, 说明n的最后一位是0
- 对于JS,ES规范在之前很多版本都是没有无符号整形的, 转化为无符号,可以用一个trick
n >>> 0
-
双”指针” 模型
-
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);
}
};
- 原题leetcode链接:https://leetcode-cn.com/problems/reverse-bits/
- 更多力扣 解题: 力扣 – 全球极客挚爱的技术成长平台 ,也可以访问我的 JS中文网 – 码农周刊 仓库:https://github.com/meibin08/free-programming-books,标星关注一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com