【面试经典150 | 】颠倒二进制位

2023-11-10 08:06

本文主要是介绍【面试经典150 | 】颠倒二进制位,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 写在前面
  • 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)


写在最后

如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。

最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。

这篇关于【面试经典150 | 】颠倒二进制位的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/381408

相关文章

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

java面试常见问题之Hibernate总结

1  Hibernate的检索方式 Ø  导航对象图检索(根据已经加载的对象,导航到其他对象。) Ø  OID检索(按照对象的OID来检索对象。) Ø  HQL检索(使用面向对象的HQL查询语言。) Ø  QBC检索(使用QBC(Qurey By Criteria)API来检索对象。 QBC/QBE离线/在线) Ø  本地SQL检索(使用本地数据库的SQL查询语句。) 包括Hibern

HotSpot虚拟机的经典垃圾收集器

读《深入理解Java虚拟机》第三版笔记。 关系 Serial、ParNew、Parallel Scavenge、Parallel Old、Serial Old(MSC)、Concurrent Mark Sweep (CMS)、Garbage First(G1)收集器。 如图: 1、Serial 和 Serial Old 收集器 2、ParNew 收集器 3、Parallel Sc

STL经典案例(四)——实验室预约综合管理系统(项目涉及知识点很全面,内容有点多,耐心看完会有收获的!)

项目干货满满,内容有点过多,看起来可能会有点卡。系统提示读完超过俩小时,建议分多篇发布,我觉得分篇就不完整了,失去了这个项目的灵魂 一、需求分析 高校实验室预约管理系统包括三种不同身份:管理员、实验室教师、学生 管理员:给学生和实验室教师创建账号并分发 实验室教师:审核学生的预约申请 学生:申请使用实验室 高校实验室包括:超景深实验室(可容纳10人)、大数据实验室(可容纳20人)、物联网实验

贝壳面试:什么是回表?什么是索引下推?

尼恩说在前面 在40岁老架构师 尼恩的读者交流群(50+)中,最近有小伙伴拿到了一线互联网企业如得物、阿里、滴滴、极兔、有赞、希音、百度、网易、美团的面试资格,遇到很多很重要的面试题: 1.谈谈你对MySQL 索引下推 的认识? 2.在MySQL中,索引下推 是如何实现的?请简述其工作原理。 3、说说什么是 回表,什么是 索引下推 ? 最近有小伙伴在面试 贝壳、soul,又遇到了相关的

毕业前第二次面试的感慨

距面试已经过去了有几天了,我现在想起来都有说多的恨感慨。 我一直都是想找刚刚起步的企业,因为这能让我学到更多的东西,然而正好有一家企业是刚起步的,而且他还有自己的产品专利,可以说这是一家,即是创业又是刚起步的公司,这家公司回复了我投给他的简历,这家企业想进一步了解我的情况,因为简历上我符合这家企业的基本要求,所以要进一步了解。 虽然面试的过程中,他给我的面试题,我做得并不是很理想,

腾讯社招面试经历

前提:本人2011年毕业于一个普通本科,工作不到2年。   15号晚上7点多,正在炒菜做饭,腾讯忽然打电话来问我对他们的Linux C++的职位是否感兴趣,我表达了我感兴趣之后,就开始了一段简短的电话面试,电话面试主要内容:C++和TCP socket通信的一些基础知识。之后就问我一道算法题:10亿个整数,随机生成,可重复,求最大的前1万个。当时我一下子就蒙了,没反应过来,何况我还正在烧

完整的腾讯面试经过

从9月10号开始到现在快两个月了,两个多月中,我经历数次面试和笔试,在经历这些的同时积累了不少的经验,也学到了不少东西,在此把它记录下来,算是和一起找工作中的同学一起共勉吧。我是本校的学生,专业是机械制造及其自动化,找工作的主要目标是计算机软件类和机械制造方向的国内的企业,所以意向去外企的同学就不必浪费时间看这些面经啦,想去国内IT企业的同学可以继续看下去。本贴中我把最近的腾讯面试经过写下

仕考网:结构化面试流程介绍

(一)结构化面试 结构化面试,也叫做标准化面试,考官按照预先设定好的一套试题以问答方式与应试者当面交谈,根据应试者的言语、行为表现,对其相关能力和个性特征作出相应评价。 (二)考试流程 抵达考场——审核抽签——面试候考——进入考场——面试答题——考生退场——计分审核 (三)答题技巧 1.声音洪亮,音量可以比平时说话声音大一点。 2.语速不要过快,语速快容易卡顿,而且不便于考官听清答