图源:文心一言
上机题目练习整理,位运算,供小伙伴们参考~🥝🥝
网页版目录在页面的右上角↗~🥝🥝
- 第1版:在力扣新手村刷题的记录~🧩🧩
编辑:梅头脑🌸
审核:文心一言
题目:面试题 05.01. 插入 - 力扣(LeetCode)
🧵面试题 05.01. 插入 - 力扣(LeetCode)
🧩题目
给定两个整型数字
N
与M
,以及表示比特位置的i
与j
(i <= 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;
位 | 31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
位 | 15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2:把M的数值左移i位
- M <<= i; // 本题中i = 2;正数左移低位可以直接补0;
位 | 31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
位 | 15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
位 | 31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
位 | 15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
3:将N的i到j位加上M
- N | M; // N 或 M,对应位中,如果其中有1个是1,则或的运算结果为1;
- 输出结果:N = 1100(10001001100)
位 | 31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
位 | 15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
📇知识扩展
位运算是直接对整数在内存中的二进制位进行操作的一种运算。由于它直接处理二进制数据,因此执行效率非常高。
简单介绍:
- 取反(NOT):
- 操作符:
~
- 功能:对一个数的所有二进制位进行取反操作,即0变为1,1变为0。
- 示例:
~0101
结果为1010
(这里的数字是二进制表示)。- 与(AND):
- 操作符:
&
- 功能:比较两个数的相应二进制位,如果两个相应位都为1,则该位的结果值为1,否则为0。
- 示例:
0101 & 0110
结果为0100
。- 或(OR):
- 操作符:
|
- 功能:比较两个数的相应二进制位,如果两个相应位中至少有一个为1,则该位的结果值为1,否则为0。
- 示例:
0101 | 0110
结果为0111
。- 异或(XOR):
- 操作符:
^
- 功能:比较两个数的相应二进制位,如果两个相应位值不同,则该位的结果值为1,否则为0。
- 示例:
0101 ^ 0110
结果为0011
。- 移位操作:
- 左移(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;
位 | 31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
位 | 15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
位 | 31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
位 | 15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
位 | 31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
位 | 15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
- unsigned int mask = leftOnes | rightOnes; // leftones与rightones相与,掩码就这样制作好了,是从2到6为0,其余都为1的数字;
- N = N & mask; // 将 N 的第 i 位到第 j 位清零(当然1024的2-6位本来就没1,清0前后是一样的);
位 | 31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
位 | 15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
位 | 31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
位 | 15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2:把M的数值左移i位
3:将N的i到j位加上M
备注:2:与3:的步骤与方法一雷同,此处不再赘述。
执行报错:我暂时也不知道怎么修复这个,哎,先留着代码再想想...
📇知识扩展
思维导图:emmm...补码规则听起来有点绕对不对,而且正数负数的存储规则是不一样的,这就涉及到计组的知识了,正好是我来不及整理和发布的那一篇,稍等我Po一下草稿——
备注:
- (发现看着图更绕了对不对)图中只有涂紫色的部分是涉及本题的,其它的是原码、反码、补码、移码的相关知识,随意看看就好~看不清图片的话可以右键存到本地打开~
- 如果对于补码的浅显原理感兴趣,可以参考这个视频:🌸2.1_4_带符号整数的表示和运算_原反补_哔哩哔哩_bilibili
- 如果对于计组的其它知识感兴趣,可以参考这个系列,菜鸟博主明年再战可能还会补充:🌸计算机组成原理_梅头脑_的博客-CSDN博客
🔚结语
博文到此结束,写得模糊或者有误之处,欢迎小伙伴留言讨论与批评,督促博主优化内容{例如有错误、难理解、不简洁、缺功能}等,博主会顶锅前来修改~~😶🌫️😶🌫️
我是梅头脑,本片博文若有帮助,欢迎小伙伴动动可爱的小手默默给个赞支持一下,感谢点赞小伙伴对于博主的支持~~🌟🌟
同系列的博文:🌸数据结构_梅头脑_的博客-CSDN博客
同博主的博文:🌸随笔03 笔记整理-CSDN博客