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)