杭州职称评审系统网站,做电子元器件的网站,软件开发专业信息,python基础教程作者文章目录 写在前面Tag题目来源题目解读解题思路方法一#xff1a;逐位颠倒方法二#xff1a;分治 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 专栏内容以分析题目为主#xff0c;并附带一些对于… 文章目录 写在前面Tag题目来源题目解读解题思路方法一逐位颠倒方法二分治 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【位运算】 题目来源
190. 颠倒二进制位 题目解读
将给定的 32 位无符号整数的二进制位进行颠倒。 解题思路
方法一逐位颠倒
n 是一个 32 位的二进制数我们从低位到高位枚举每一位将其放置到答案 res 的合适位置。比如 n 的二进制位的第 i 位从低位往高位数放置到 res 的第 31 - i 位。当前枚举的比特位为当前 n 1在枚举完成当前位后更新 n 1 为下一个枚举做准备。
实现代码
class Solution {
public:uint32_t reverseBits(uint32_t n) {uint32_t ans 0;for(int i 0; i 32; i){int lst n 1;lst (31-i);ans | lst;n 1;}return ans;}
};复杂度分析
时间复杂度 O ( l o g n ) O(logn) O(logn)。
空间复杂度 O ( 1 ) O(1) O(1)。
方法二分治
还有一种分治的方法来实现 32 位无符号整数的二进制数颠倒。分治法又分为两种
自上而下自下而上。
我们先来看一下自上而下进行分治自上而下首先对二进制数每 16 位为一组进行交换接着是每 8 位一组交换、4 位一组交换、2 位一组交换直至 1 位二进制数为一组进行交换。通过这样的交换之后就可以实现 32 位无符号整数的二进制数颠倒
怎么实现 16 位二进制数一组进行交换呢通过位运算啊将 n 右移 16 位那么 n 将只会保留高位的 16 位将 n 左移 16 位那么 n 将只会保留低位的 16 位 (n 16) | (n 16) 就完成了第一步的 “对二进制数每 16 位为一组进行交换”。 如图所示我们以 8 位为一组进行交换n 0x00ff00ff 就可以得到 1 组和 3 组位置的 8 位二进制数我们再对 n 0x00ff00ff 左移八位就将 1 组和 3 组位置的 8 位二进制数移动到了 0 组和 2 组。我们现将 n 左移 8 位然后与上 0x00ff00ff 就将 0 组和 2 组位置的 8 位二进制数移动到了 1 组和 3 组。最后将这两种操作或上就完成了以 8 位为一组进行交换。
类似的可以完成以 4、2、1 为一组的交换操作。
以上遍历自上而下的分治方法。自下而上的分治操作就是先以 1 为一组进行交换然后再分别以 2、4、16 为一组进行交换。需要注意的是每种交换单位对应需要与上的二进制数。
以下代码给出的是自下而上的分治代码自上而下的分治代码就是自下而上的分治代码顺序颠倒过来。方法二也是 【进阶】的解决方案。
实现代码
class Solution {
private:const uint32_t M1 0x55555555;const uint32_t M2 0x33333333;const uint32_t M4 0x0f0f0f0f;const uint32_t M8 0x00ff00ff;
public:uint32_t reverseBits(uint32_t 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;}
};复杂度分析
时间复杂度 O ( 1 ) O(1) O(1)。
空间复杂度 O ( 1 ) O(1) O(1)。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
