LeetCode 0190 Reverse Bits
2022/5/30 23:21:32
本文主要是介绍LeetCode 0190 Reverse Bits,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题传送门
1. 题目描述
2. Solution 1
1、思路分析
逐位颠倒
We first initialize result to 0. We then iterate from
0 to 31 (an integer has 32 bits). In each iteration:
We first shift result to the left by 1 bit.
Then, if the last digit of input n is 1, we add 1 to result. To
find the last digit of n, we just do: (n & 1)
Example, if n=5 (101), n&1 = 101 & 001 = 001 = 1;
however, if n = 2 (10), n&1 = 10 & 01 = 00 = 0).
Finally, we update n by shifting it to the right by 1 (n >>= 1). This is because the last digit is already taken
care of, so we need to drop it by shifting n to the right by 1.
2、代码实现
package Q0199.Q0190ReverseBits; /* We first initialize result to 0. We then iterate from 0 to 31 (an integer has 32 bits). In each iteration: We first shift result to the left by 1 bit. Then, if the last digit of input n is 1, we add 1 to result. To find the last digit of n, we just do: (n & 1) Example, if n=5 (101), n&1 = 101 & 001 = 001 = 1; however, if n = 2 (10), n&1 = 10 & 01 = 00 = 0). Finally, we update n by shifting it to the right by 1 (n >>= 1). This is because the last digit is already taken care of, so we need to drop it by shifting n to the right by 1. */ public class Solution { // you need treat n as an unsigned value public int reverseBits(int n) { if (n == 0) return 0; int result = 0; for (int i = 0; i < 32; i++) { result <<= 1; // 把当前结果保存到result的最低位 if ((n & 1) == 1) result++; n >>= 1; } return result; } }
3、复杂度分析
时间复杂度: O(32) = O(1)
空间复杂度: O(1)
3. Solution 2
1、思路分析
位运算分治
若要翻转一个二进制串,可以将其均分成左右两部分,对每部分递归执行翻转操作,然后将左半部分拼在右半部分的后面,即完成了翻转。
由于左右两部分的计算方式是相似的,利用位掩码和位移运算,可以自底向上地完成这一分治流程。
对于递归的最底层,需要交换所有奇偶位: 取出所有奇数位和偶数位;将奇数位移到偶数位上,偶数位移到奇数位上。类似地,对于倒数第二层,每两位分一组,按组号取出所有奇数组和偶数组,然后将奇数组移到偶数组上,偶数组移到奇数组上。
2、代码实现
public class Solution { private static final int M1 = 0x55555555; // 01010101010101010101010101010101 private static final int M2 = 0x33333333; // 00110011001100110011001100110011 private static final int M4 = 0x0f0f0f0f; // 00001111000011110000111100001111 private static final int M8 = 0x00ff00ff; // 00000000111111110000000011111111 public int reverseBits(int n) { n = n >>> 1 & M1 | (n & M1) << 1; n = n >>> 2 & M2 | (n & M2) << 2; n = n >>> 4 & M4 | (n & M4) << 4; n = n >>> 8 & M8 | (n & M8) << 8; return n >>> 16 | n << 16; } }
3、复杂度分析
时间复杂度: O(1)
空间复杂度: O(1)
这篇关于LeetCode 0190 Reverse Bits的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!
- 2024-05-08今天开始程序员不用再发愁写commit message了,全部由CodeGeeX自动完成!