题目
颠倒给定的 32 位无符号整数的二进制位。 来自：https://leetcode.cn/problems/reverse-bits/description/
解法一
-
取 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)：n 为二进制位的个数，这里为32。
空间复杂度 O(1)。
解法二
代码实现
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)：时间复杂度取决于 n 中最高为1的位置，即 logn 向下取整 + 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)。
本篇文章来源于微信公众号: i余数
微信扫描下方的二维码阅读本文
Comments NOTHING