【算法题解】3. 颠倒二进制位

短命女 2024-03-30 11:59 47阅读 0赞

#### 文章目录 ####

*   *  题目
     *  解法一
     *   *  解题思路
         *  代码实现
         *  复杂度分析
     *  解法二
     *   *  解题思路
         *  代码实现
         *  复杂度分析
     *  解法三
     *   *  解题思路
         *  代码实现
         *  复杂度分析

### 题目 ###

> 颠倒给定的 32 位无符号整数的二进制位。来自：[leetcode][]

### 解法一 ###

#### 解题思路 ####

1.  取 n 的最低位，赋值给 ans 的最低位（ans 初始值位0）。
2.  然后 n 向后移动一位，ans 向前移动一位，重复步骤1，直到取完 n 的所有位置。  
    ![【算法题解3】 颠倒二进制位][3_]

#### 代码实现 ####

public class Solution {
        
        // you need treat n as an unsigned value
        public int reverseBits(int n) {
        
            int ans = n & 1;
            for(int i = 0; i < 31; i++){
        
                n = n >>> 1;
                ans = ans << 1;
                ans |= n & 1;
                
            }
            return ans;
        }
    }

#### 复杂度分析 ####

时间复杂度  O ( n ) O(n) O(n)：n 为二进制位的个数，这里为32。  
空间复杂度  O ( 1 ) O(1) O(1)。

### 解法二 ###

#### 解题思路 ####

从 n 的最低位开始一位一位的取，然后将取到的值从 ans 的最高位开始一位一位的放，ans 的初始值为0。

用 `n & 1` 获取到 n 当前的最后一位，赋值给 ans 的最高位。然后将 n 右移 1 位，再用`n & 1` 就可以取到 n 的倒数第二位，以此类推，直到取完 n 的最高位的 1 之后，由于剩下的位置都是 0 ，和 ans 的初始值是一样的无需计算，则可以直接结束。

以 `n = 0001 1100 1101 0100` 为例，结果为：`ans = 0010 1011 0011 1000`。

![【算法题解3】 颠倒二进制位][3_ 1]

#### 代码实现 ####

public class Solution {
        
        // you need treat n as an unsigned value
        public int reverseBits(int n) {
        
            
            int ans = 0;
            for(int i = 0; i < 32 && n != 0; i++){
        
                ans |= (n & 1) << (31 - i);
                n = n >>> 1;
            }
            
            return ans;
        }
    }

#### 复杂度分析 ####

时间复杂度  O ( l o g n ) O(logn) O(logn)：时间复杂度取决于 n 中最高为1的位置，即 logn 向下取整 + 1。  
空间复杂度  O ( 1 ) O(1) O(1)。

### 解法三 ###

#### 解题思路 ####

使用分治的思想：

1.  将32位二进制位分为2个16位的二进制位，分别颠倒2个16位的二进制位，然后再将颠倒后的2个16位数互换位置。
2.  现在问题装换为颠倒一个16位二进制数，那么同样将16位二进制位分为2个8位的二进制位，分别颠倒2个8位的二进制位，然后再将颠倒后的2个8位数互换位置。
3.  现在问题装换为颠倒一个8位二进制数，那么同样将8位二进制位分为2个4位的二进制位，分别颠倒2个4位的二进制位，然后再将颠倒后的2个4位数互换位置。
4.  现在问题装换为颠倒一个4位二进制数，那么同样将4位二进制位分为2个2位的二进制位，分别颠倒2个2位的二进制位，然后再将颠倒后的2个2位数互换位置。
5.  现在问题装换为颠倒一个2位二进制数，那么直接交换2个二进制位的位置即可，即交换二进制奇偶位。  
    总结：要求颠倒32位 -> 需要先求颠倒16位 -> 需要先求颠倒8位 -> 需要先求颠倒4位 -> 需要先求颠倒2位（交换二进制奇偶位）,一个递归的算法。

以16位 `n = 0001 1100 1101 0100` 为例，结果为：`ans = 0010 1011 0011 1000`。

![【算法题解3】 颠倒二进制位][3_ 2]

#### 代码实现 ####

public class Solution {
        
        // you need treat n as an unsigned value
        public int reverseBits(int n) {
        
            
            //奇偶反转
            n = (n & 0x55555555) << 1 | (n >>> 1) & 0x55555555;
    
            //两两反转， 求的4位二进制的反转
            n = (n & 0x33333333) << 2 | (n >>> 2) & 0x33333333;
    
            // 每4个进行反转，求的8位二进制的反转
            n = (n & 0x0f0f0f0f) << 4 | (n >>> 4) & 0x0f0f0f0f;
    
            // 每8个进行反转，求的16位二进制的反转
            n = (n & 0x00ff00ff) << 8 | (n >>> 8) & 0x00ff00ff;
    
            // 每16个进行反转，求的32位二进制的反转
            n = (n & 0x0000ffff) << 16 | (n >>> 16) & 0x0000ffff;
    
            return n;
        }
    }

#### 复杂度分析 ####

时间复杂度  O ( 1 ) O(1) O(1)。  
空间复杂度  O ( 1 ) O(1) O(1)。

[leetcode]: https://leetcode.cn/problems/reverse-bits/description/
[3_]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8b4fbdd9223646d99d132c851bbc7c16.png
[3_ 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/5ad1cb5922874396b07a082ea195038a.png
[3_ 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/dd020704f4404e27b32726deec0f2695.png