文章目录

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

题目

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

解法一

解题思路

1. 取 n 的最低位，赋值给 ans 的最低位（ans 初始值位0）。
2. 然后 n 向后移动一位，ans 向前移动一位，重复步骤1，直到取完 n 的所有位置。
   

代码实现

public class Solution {// you need treat n as an unsigned valuepublic 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。

代码实现

public class Solution {// you need treat n as an unsigned valuepublic 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(logn)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。

代码实现

public class Solution {// you need treat n as an unsigned valuepublic 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)。