位运算01 插入[C++]

图源:文心一言

上机题目练习整理,位运算,供小伙伴们参考~🥝🥝

网页版目录在页面的右上角↗~🥝🥝

  • 第1版:在力扣新手村刷题的记录~🧩🧩

编辑:梅头脑🌸

审核:文心一言

题目:面试题 05.01. 插入 - 力扣(LeetCode)


🧵面试题 05.01. 插入 - 力扣(LeetCode)

🧩题目

给定两个整型数字 N 与 M,以及表示比特位置的 i 与 ji <= j,且从 0 位开始计算)。

编写一种方法,使 M 对应的二进制数字插入 N 对应的二进制数字的第 i ~ j 位区域,不足之处用 0 补齐。具体插入过程如图所示。

题目保证从 i 位到 j 位足以容纳 M, 例如: M = 10011,则 i~j 区域至少可容纳 5 位。

示例1:

 输入:N = 1024(10000000000), M = 19(10011), i = 2, j = 6
 输出:N = 1100(10001001100)

示例2:

 输入: N = 0, M = 31(11111), i = 0, j = 4
 输出:N = 31(11111)

🌰方法一:循环+按位运算

📇算法思路

  • 算法思想:
    • 将N的第i位到第j位清零(置为0),可以使用按位与和按位取反操作。
    • 将M左移,使得它的最低位对齐N的第i位。
    • 使用按位或操作,将步骤1和步骤2的结果合并。
  • 时间复杂度:O(1);
  • 空间复杂度:O(1);

⌨️算法代码

class Solution {
public:
    int insertBits(int N, int M, int i, int j) {
        // 1.把N的i到j位置为0
        for (int k = i; k <= j; k++) {
            if (N & (1 << k)) {
                N ^= (1 << k);
            }
        }
        // 2.把M的数值左移i位
        M <<= i;
        // 3.将N的i到j位加上M
        return N | M;
    }
};

作者:coeker
链接:https://leetcode.cn/problems/insert-into-bits-lcci/solutions/712628/cwei-yun-suan-by-coeker-stgw/

📇代码解释

 1:把N的i到j位置为0

  • N & (1 << k)):N的2~6位 (&)与 1,可以区分2~6位是0还是1;如果2到6为1,满足判断条件,则执行异或语句;
  • N ^= (1 << k):将N的2~6位中二进制为“1”的位数 异或(1)1,根据同1异0,这些位置都会变为0,达到置零效果;
  • 执行结果:虽然本题N = 1024,其2~6位已经是0,条件语句执行前后的结果是完全相同的,还是1024;
N
31302928272625242322212019181716
0000000000000000
15141312111009080706050403020100
0000010000000000

2:把M的数值左移i位

  • M <<= i; // 本题中i = 2;正数左移低位可以直接补0;
M移动前
31302928272625242322212019181716
0000000000000000
15141312111009080706050403020100
0000000000010011
M移动后
31302928272625242322212019181716
0000000000000000
15141312111009080706050403020100
0000000001001100

3:将N的i到j位加上M

  • N | M;  // N 或 M,对应位中,如果其中有1个是1,则或的运算结果为1;
  • 输出结果:N = 1100(10001001100)
N | M
31302928272625242322212019181716
0000000000000000
15141312111009080706050403020100
0000100001001100

📇知识扩展

位运算是直接对整数在内存中的二进制位进行操作的一种运算。由于它直接处理二进制数据,因此执行效率非常高。

简单介绍:

  1. 取反(NOT)
    • 操作符:~
    • 功能:对一个数的所有二进制位进行取反操作,即0变为1,1变为0。
    • 示例:~0101 结果为 1010(这里的数字是二进制表示)。
  2. 与(AND)
    • 操作符:&
    • 功能:比较两个数的相应二进制位,如果两个相应位都为1,则该位的结果值为1,否则为0。
    • 示例:0101 & 0110 结果为 0100
  3. 或(OR)
    • 操作符:|
    • 功能:比较两个数的相应二进制位,如果两个相应位中至少有一个为1,则该位的结果值为1,否则为0。
    • 示例:0101 | 0110 结果为 0111
  4. 异或(XOR)
    • 操作符:^
    • 功能:比较两个数的相应二进制位,如果两个相应位值不同,则该位的结果值为1,否则为0。
    • 示例:0101 ^ 0110 结果为 0011
  5. 移位操作
    • 左移(Left Shift):<<
      • 功能:将二进制数所有位向左移动指定的位数,高位丢弃,低位用0补充。
      • 示例:0010 << 1 结果为 0100
    • 右移(Right Shift):>>(有符号和无符号之分,具体行为取决于编程语言)
      • 功能:将二进制数所有位向右移动指定的位数,低位丢弃,高位可能用0或1补充(取决于原数的符号)。
      • 示例:0010 >> 1 结果为 0001

特殊用途

  • 指定位置0
    • 使用与运算(AND)可以将指定位置0。
    • 示例:假设要将数num的第i位(从0开始计数)置0,可以使用num & ~(1 << i)
  • 指定位置1
    • 使用或运算(OR)可以将指定位置1。
    • 示例:假设要将数num的第i位(从0开始计数)置1,可以使用num | (1 << i)
  • 指定位翻转
    • 使用异或运算(XOR)可以实现指定位的翻转(0变为1,1变为0)。
    • 示例:假设要翻转数num的第i位(从0开始计数),可以使用num ^ (1 << i)

位运算在编程中有很多用途,包括优化性能、处理二进制数据、加密解密、网络通信中的数据打包与解包等。

🌰解题二:创建掩码<错误代码自留>

📇算法思路

  • 基本思想同算法一,不再赘述~
  • 这个代码提交会出错,自留,以后可能会回来修改~

⌨️算法代码

#include <iostream>  
#include <cassert> 
using namespace std;

class Solution {
public:
    int insertBits(int N, int M, int i, int j) {
        // 确保 i 和 j 是有效的索引  
        assert(0 <= i && i <= j && j < 32);

        // 创建掩码以清零 N 的第 i 位到第 j 位  
        unsigned int allOnes = ~0U; // 使用无符号整数  
        unsigned int leftOnes = allOnes >> (j + 1); // 现在这是安全的,因为 allOnes 是无符号的  
        unsigned int rightOnes = ((1U << i) - 1); // 注意这里应该是 (1 << i),并且使用无符号整数  
        unsigned int mask = leftOnes | rightOnes;

        // 将 N 的第 i 位到第 j 位清零  
        N = N & mask;

        // 将 M 左移,使得它的最低位对齐 N 的第 i 位  
        M = M << i;

        // 使用按位或操作,将步骤1和步骤2的结果合并  
        N = N | M;

        // N 现在是一个无符号整数,但我们知道它不会溢出,所以可以安全地将其转换回有符号整数  
        return static_cast<int>(N);
    }
};

int main() {
    Solution solution;

    int N = 1024; // 10000000000  
    int M = 19; // 10011  
    int i = 2;
    int j = 6;

    int result = solution.insertBits(N, M, i, j);
    cout << "Output: N = " << result << " (in decimal, expected binary representation: 10001001100)" << endl;

    // 第二个示例  
    N = 0;
    M = 31; // 11111  
    i = 0;
    j = 4;

    result = solution.insertBits(N, M, i, j);
    cout << "Output: N = " << result << " (in decimal, expected binary representation: 11111)" << endl;

    return 0;
}

 作者:文心一言

📇代码解释

1:清零 N 的第 i 位到第 j 位

  • unsigned int allOnes = ~0U; ~是按位非操作,无符号0的二进制为00...000,按位取反后为11...111,本步骤创建一个全是1的掩码;
  • unsigned int leftOnes = allOnes << (j + 1);  allOnes左移 j + 1 位,创建左边全是1,到 j + 1 位为0的掩码,本例 j = 6 ;(备注一下,这里如果是int,那么就需要逻辑左移而非算术左移,否则负数左移补1,无论它怎么左移它都是111...111);
  • int rightOnes = (1 << i) - 1; // 1左移2位然后-1,创建右边全是1,到i位为0的掩码 ,本例 i = 2;
allOnes
31302928272625242322212019181716
1111111111111111
15141312111009080706050403020100
1111111111111111
leftOnes
31302928272625242322212019181716
1111111111111111
15141312111009080706050403020100
1111111110000000
rightOnes
31302928272625242322212019181716
0000000000000000
15141312111009080706050403020100
0000000000000011
  • unsigned int mask = leftOnes | rightOnes;  // leftones与rightones相与,掩码就这样制作好了,是从2到6为0,其余都为1的数字;
  • N = N & mask; // 将 N 的第 i 位到第 j 位清零(当然1024的2-6位本来就没1,清0前后是一样的);
mask
31302928272625242322212019181716
1111111111111111
15141312111009080706050403020100
1111111110000011
N(修改后)
31302928272625242322212019181716
0000000000000000
15141312111009080706050403020100
0000010000000000

2:把M的数值左移i位

3:将N的i到j位加上M

备注:2:与3:的步骤与方法一雷同,此处不再赘述。

执行报错:我暂时也不知道怎么修复这个,哎,先留着代码再想想...

📇知识扩展

思维导图:emmm...补码规则听起来有点绕对不对,而且正数负数的存储规则是不一样的,这就涉及到计组的知识了,正好是我来不及整理和发布的那一篇,稍等我Po一下草稿——

备注:

  • (发现看着图更绕了对不对)图中只有涂紫色的部分是涉及本题的,其它的是原码、反码、补码、移码的相关知识,随意看看就好~看不清图片的话可以右键存到本地打开~
  • 如果对于补码的浅显原理感兴趣,可以参考这个视频:🌸2.1_4_带符号整数的表示和运算_原反补_哔哩哔哩_bilibili
  • 如果对于计组的其它知识感兴趣,可以参考这个系列,菜鸟博主明年再战可能还会补充:🌸计算机组成原理_梅头脑_的博客-CSDN博客

🔚结语

博文到此结束,写得模糊或者有误之处,欢迎小伙伴留言讨论与批评,督促博主优化内容{例如有错误、难理解、不简洁、缺功能}等,博主会顶锅前来修改~~😶‍🌫️😶‍🌫️

我是梅头脑,本片博文若有帮助,欢迎小伙伴动动可爱的小手默默给个赞支持一下,感谢点赞小伙伴对于博主的支持~~🌟🌟

同系列的博文:🌸数据结构_梅头脑_的博客-CSDN博客

同博主的博文:🌸随笔03 笔记整理-CSDN博客

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/377072.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vue3-内置组件-KeepAlive

KeepAlive <KeepAlive> 是一个内置组件&#xff0c;它的功能是在多个组件间动态切换时缓存被移除的组件实例。 基本使用 默认情况下&#xff0c;一个组件实例在被替换掉后会被销毁。这会导致它丢失其中所有已变化的状态——当这个组件再一次被显示时&#xff0c;会创建…

深入探究 HTTP 简化:httplib 库介绍

✏️心若有所向往&#xff0c;何惧道阻且长 文章目录 简介特性主要类介绍httplib::Server类httplib::Client类httplib::Request类httplib::Response类 示例服务器客户端 总结 简介 在当今的软件开发中&#xff0c;与网络通信相关的任务变得日益普遍。HTTP&#xff08;Hypertext…

Linux | 进度条 | Linux简单小程序 | 超级简单 | 这一篇就够了

进度条—实例示范 在学习了基本的Linux指令&#xff0c;Linux上vim编译器等等之后&#xff0c;我们就来学习写代码喽~ 今天就给大家详细讲解一下进度条的编写&#xff0c;需要的效果如下图&#xff1a; 进度条—必备知识 回车和换行 在我们学习编程语言中&#xff0c;经常…

2024年【G1工业锅炉司炉】考试及G1工业锅炉司炉考试内容

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年G1工业锅炉司炉考试为正在备考G1工业锅炉司炉操作证的学员准备的理论考试专题&#xff0c;每个月更新的G1工业锅炉司炉考试内容祝您顺利通过G1工业锅炉司炉考试。 1、【多选题】TSGG0001-2012《锅炉安全技术监察…

高中学校档案室主要做什么

高中学校档案室主要负责管理、保存和维护学校的各类档案文件。具体工作内容包括&#xff1a; 1. 档案收集&#xff1a;负责收集学校各个部门的档案文件&#xff0c;包括学生档案、教职工档案、教学档案、行政档案等。 2. 档案分类和整理&#xff1a;对收集到的档案文件进行分类…

Nginx限流设置

1.反向代理(建议先看正向代理,反向代理则是同样你要与对方服务器建立连接,但是,代理服务器和目标服务器在一个LAN下,所以我们需要与代理服务器先建交,再由他获取与目标服务器的交互,好比一个带刀侍卫守护着目标服务器) 屏蔽目标服务器的真实地址&#xff0c;相对安全性较好&am…

相机图像质量研究(6)常见问题总结:光学结构对成像的影响--对焦距离

系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结&#xff1a;光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结&#xff1a;光学结构对成…

鸿蒙OS导入项目报错不能运行 @ohos\hvigor\bin\hvigor.js‘

在自学HarmonyOS时&#xff0c;想在DevEco Studio导入官方示例代码&#xff1a;待办列表&#xff08;ArkTS&#xff09;报错 C:\Users\woods\Downloads\test01\ToDoListArkTS\node_modules\ohos\hvigor\bin\hvigor.js --mode module -p moduleentrydefault -p productdefault …

SpringBoot集成Swagger2的增强版Knife4j

1. 背景 作为SpringBoot集成中间件其中的一篇文章吧&#xff0c;既然打算出这么一个系列了&#xff0c;争取做到虽小却全&#xff0c;又精又美的一个系列吧。 Swagger应该都有接触吧&#xff0c;knife4j是Swagger2的增强版&#xff0c;更加友好的操作页面&#xff0c;更多强大…

Java实现民宿预定管理系统 JAVA+Vue+SpringBoot+MySQL

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 用例设计2.2 功能设计2.2.1 租客角色2.2.2 房主角色2.2.3 系统管理员角色 三、系统展示四、核心代码4.1 查询民宿4.2 新增民宿4.3 新增民宿评价4.4 查询留言4.5 新增民宿订单 五、免责说明 一、摘要 1.1 项目介绍 基于…

力扣优选算法100道——【模板】前缀和(一维)

【模板】前缀和_牛客题霸_牛客网 (nowcoder.com) 目录 &#x1f6a9;了解题意 &#x1f6a9;算法原理 &#x1f388;设定下标为1开始 &#x1f388;取值的范围 &#x1f6a9;实现代码 &#x1f6a9;了解题意 第一行的3和2&#xff0c;3代表行数&#xff0c;2代表q次查询(…

【Python4Delphi】学习笔记(一):介绍篇

一、前言&#xff1a; 1. python语言简介&#xff1a; 众所周知&#xff0c;python是目前非常流行的编程语言之一&#xff0c;自20世纪90年代初Python语言诞生至今&#xff0c;它已被逐渐广泛应用于系统管理任务的处理和Web编程。 由于Python语言的简洁性、易读性以及可扩展性…

[React] ref属性

简介 ref 即 reference &#xff0c;是 React 提供给我们的安全访问 DOM 元素或者某个组件实例的句柄。 组件被调用时会新建一个该组件的实例&#xff0c;而 ref 就会指向这个实例。它可以是一个回调函数&#xff0c;这个回调函数会在组件被挂载后立即执行。 为了防止内存泄漏…

C语言笔试题之实现C库函数 pow()(递归的思想)

实例要求&#xff1a; 1、请你实现C库函数 pow()&#xff08;stdio.h & math.h&#xff09; &#xff0c;即计算 x 的整数 n 次幂函数&#xff08;即x^n &#xff09;&#xff1b;2、函数声明&#xff1a;double myPow(double x, int n)&#xff1b;参数&#xff1a;1、x …

2019年江苏省职教高考计算机技能考试——一道程序改错题的分析

题目&#xff1a;函数将str字符串中的5个数字字符串转换为整数&#xff0c;并保存在二维数组m的最后一行&#xff0c;各元素为3、-4、16、18、6。并经函数move处理后&#xff0c;运行结果如下&#xff1a; 18 6 3 -4 16 16 18 6 3 -4 -4 16 …

Springboot整合JUnit5框架

目录 第一章、在pom文件中导入依赖第二章、新建测试类第三章、新建测试方法 友情提醒: 先看文章目录&#xff0c;大致了解文章知识点结构&#xff0c;点击文章目录可直接跳转到文章指定位置。 第一章、在pom文件中导入依赖 SpringBoot2.2x之后的版本中spring-boot-starter-te…

如何使用phpStudy搭建网站并结合内网穿透远程访问本地站点

文章目录 [toc]使用工具1. 本地搭建web网站1.1 下载phpstudy后解压并安装1.2 打开默认站点&#xff0c;测试1.3 下载静态演示站点1.4 打开站点根目录1.5 复制演示站点到站网根目录1.6 在浏览器中&#xff0c;查看演示效果。 2. 将本地web网站发布到公网2.1 安装cpolar内网穿透2…

2023年全球软件开发大会(QCon上海站2023):核心内容与学习收获(附大会核心PPT下载)

在信息化和全球化日益加速的今天&#xff0c;软件开发技术日新月异&#xff0c;对全球各行各业产生了深远影响。2023年全球软件开发大会&#xff08;QCon上海站2023&#xff09;无疑成为行业内外瞩目的焦点。本次大会汇集了全球顶级的软件开发专家、企业领袖、研究者&#xff0…

1978-2022年各省家庭恩格尔系数(分城镇、农村)

1978-2022年各省家庭恩格尔系数&#xff08;分城镇、农村&#xff09; 1、时间&#xff1a;1978-2022年 2、指标&#xff1a;城镇家庭恩格尔系数、农村家庭恩格尔系数 3、来源&#xff1a;统计年鉴、省统计公报 4、范围&#xff1a;31省 5、指标解释&#xff1a;恩格尔系数…

sqli-labs-master靶场训练笔记(38-53|boss战)

2024.2.4 level-38 &#xff08;堆叠注入&#xff09; 这题乍一看感觉又是来卖萌的&#xff0c;这不是和level-1一模一样吗 然后仔细看了一下源代码&#xff0c;根据 mysqli_multi_query 猜测这题的本意应该是堆叠注入 mysqli_multi_query() 是 PHP 中用于执行多个 SQL 查…