0190. 颠倒二进制位 · ttttt

# 0190. 颠倒二进制位 ## 题目地址(190. 颠倒二进制位) <https://leetcode-cn.com/problems/reverse-bits/> ## 题目描述 ``` <pre class="calibre18">``` 颠倒给定的 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 - 对于JS，ES规范在之前很多版本都是没有无符号整形的，转化为无符号，可以用一个trick`n >>> 0` - 双"指针" 模型 - bit 运算 ## 代码 - 语言支持：JS，C++，Python JavaScript Code： ``` <pre class="calibre18">``` /** * @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： ``` <pre class="calibre18">``` 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: ``` <pre class="calibre18">``` 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(logN)O(logN) - 空间复杂度：O(1)O(1)O(1) ## 拓展不使用迭代也可以完成相同的操作： 1. 两两相邻的1位对调 2. 两两相邻的2位对调 3. 两两相邻的4位对调 4. 两两相邻的8位对调 5. 两两相邻的16位对调 C++代码如下： ``` <pre class="calibre18">``` 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啦。关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)