找人建设一个网站多少钱,注册网站送金币,北京企业官网建设,网页编辑word文档算法沉淀——位运算 常用位运算总结1.基础位运算2.确定一个数中第x位是0还是13.将一个数的第x位改成14.将一个数的第x位改成05.位图6.提取一个数最右边的17.删掉一个数最右边的18.异或运算9.基础例题 力扣题目讲解01.面试题 01.01. 判定字符是否唯一02.丢失的数字03.两整数之和… 算法沉淀——位运算 常用位运算总结1.基础位运算2.确定一个数中第x位是0还是13.将一个数的第x位改成14.将一个数的第x位改成05.位图6.提取一个数最右边的17.删掉一个数最右边的18.异或运算9.基础例题 力扣题目讲解01.面试题 01.01. 判定字符是否唯一02.丢失的数字03.两整数之和04.只出现一次的数字 II05.面试题 17.19. 消失的两个数字 常用位运算总结
1.基础位运算 按位与对两个二进制数的对应位进行与运算结果中的每一位都是两个数对应位上的位与操作的结果。 int result a b;按位或|对两个二进制数的对应位进行或运算结果中的每一位都是两个数对应位上的位或操作的结果。 int result a | b;按位异或^对两个二进制数的对应位进行异或运算结果中的每一位都是两个数对应位上的位异或操作的结果。 int result a ^ b;按位取反~对一个二进制数的每一位取反即将0变为1将1变为0。 int result ~a;左移将一个二进制数的所有位向左移动指定的位数右侧用0填充。 int result a 2; // 将a的二进制表示向左移动2位右移) 将一个二进制数的所有位向右移动指定的位数左侧用符号位填充对于有符号整数无符号整数左侧用0填充。 int result a 1; // 将a的二进制表示向右移动1位2.确定一个数中第x位是0还是1
(nx)1 n x右移操作符将二进制表示的整数 n 向右移动 x 位。这意味着我们把整数 n 的二进制表示向右移动 x 位。(n x) 1与操作符 对两个二进制数的对应位进行与运算。在这里对 (n x) 的结果与二进制数 1 进行与运算。 如果 (n x) 的二进制表示中第 x 位是1与1进行与运算的结果是1。如果 (n x) 的二进制表示中第 x 位是0与1进行与运算的结果是0。
这是一种常见的技巧特别是在位操作中用于提取或测试一个特定位的值。
3.将一个数的第x位改成1
n|(1x)1 x左移操作符将二进制数 1 向左移动 x 位。这意味着我们在二进制数 1 的基础上将其向左移动 x 位从而在第 x 位设置为1其它位为0。n | (1 x)按位或赋值操作符 | 将 n 的二进制表示与 (1 x) 的二进制表示进行按位或运算并将结果存储回 n。这样n 的第 x 位被设置为1其它位保持不变。 如果 n 的第 x 位原本是0进行按位或运算后仍然为1。如果 n 的第 x 位原本是1进行按位或运算后仍然为1。
4.将一个数的第x位改成0
n(~(1x))1 x左移操作符将二进制数 1 向左移动 x 位。这意味着我们在二进制数 1 的基础上将其向左移动 x 位从而在第 x 位设置为1其它位为0。~(1 x)按位取反操作符 ~ 将 (1 x) 的每一位取反即将第 x 位由1变为0其它位由0变为1。n (~(1 x))按位与赋值操作符 将 n 的二进制表示与 (~(1 x)) 的二进制表示进行按位与运算并将结果存储回 n。这样n 的第 x 位被设置为0其它位保持不变。 如果 n 的第 x 位原本是1进行按位与运算后变为0。如果 n 的第 x 位原本是0进行按位与运算后仍然为0。
5.位图
基本概念位图是一个由二进制位组成的数组其中每一位都表示一个元素的存在或缺失。通常每个元素都与位图中的一个二进制位相对应。表示集合位图主要用于表示集合其中集合中的每个元素都有一个唯一的标识符例如整数。如果集合中的元素存在对应位置的位被设置为1如果元素不存在对应位置的位被设置为0。节省空间相比于其他数据结构位图在存储上更加紧凑。一个位可以表示一个元素的存在与否因此对于包含大量小范围整数的集合位图可以显著减少存储空间的需求。
示例
考虑一个集合 {1, 3, 5, 7, 9}对应的位图可能如下所示
1 0 1 0 1 0 1 0 1 0这表示集合中的元素存在对应位置的位为1。通过位图我们可以方便地进行快速的集合操作和检索。
具体可以看我之前写过的一篇博客
https://blog.csdn.net/kingxzq/article/details/133775093
6.提取一个数最右边的1
n-n计算 -n在计算机中负数通常以补码形式表示。 -n 可以通过将 n 的各位取反按位取反然后加1得到。也就是说-n 是 n 的按位取反再加1。位与操作 n -n将 n 与 -n 进行按位与操作。这将保留 n 中最右边的1而将其他位都置为0。
这个技巧的背后是n 和 -n 在二进制表示中只有最右边的1是相同的其他位都是相反的。因此按位与操作会保留这个共同的最右边的1其他位会被置零。
例如如果 n 的二进制表示是 1011000那么 -n 的二进制表示是 0101000进行按位与操作后得到 0001000即提取了 n 中最右边的1。
7.删掉一个数最右边的1
n(n-1)计算 n-1将整数 n 减去1。这相当于将 n 的最右边的1变为0并且将该1右侧的所有位都取反。位与操作 n (n-1)将 n 与 n-1 进行按位与操作。这将保留 n 中除了最右边的1之外的所有位。
通过这个操作n 中最右边的1及其右侧的所有位都会被清零而其他位保持不变。
例如如果 n 的二进制表示是 1011000那么 n-1 的二进制表示是 1010111进行按位与操作后得到 1010000即删除了 n 中最右边的1。
8.异或运算 a ^ 0 a任何数与0进行异或运算的结果都是它本身。这是因为异或运算的规则是如果两个对应位的输入相同则输出为0如果不同则输出为1。因此一个数与0进行异或对应的位都保持不变结果就是这个数本身。 例如a 10100 0000则 a ^ 0 1010。 a ^ a 0任何数与自己进行异或运算的结果都是0。这是因为对应位相同的情况下输出为0而数与自己的对应位肯定相同因此结果为0。 例如a 1010则 a ^ a 0000。 a ^ b ^ c a ^ (b ^R c)异或运算满足结合律即无论是如何加括号得到的结果都是相同的。这是因为异或运算的结果取决于每一位的对应关系而不受操作数的先后顺序影响。 例如a 1010b 1100c 0110则 (a ^ b) ^ c 0010a ^ (b ^ c) 0010。
9.基础例题
191. 位1的个数
338. 比特位计数
461. 汉明距离
136. 只出现一次的数字
260. 只出现一次的数字 III
力扣题目讲解
01.面试题 01.01. 判定字符是否唯一
题目链接https://leetcode.cn/problems/is-unique-lcci/
实现一个算法确定一个字符串 s 的所有字符是否全都不同。
示例 1
输入: s leetcode
输出: false 示例 2
输入: s abc
输出: true限制
0 len(s) 100 s[i]仅包含小写字母如果你不使用额外的数据结构会很加分。
思路
这里我们先想到的可能是哈希的思路再进一步优化我们可以使用数组来模拟哈希但还不是最优的解法因为题目要求这里是只有小写字母因此我们可以用一个整形利用位图思想来进行每一个比特位所以这里我们只需要确定这个整形中的x位是0还是1以及将第x位改成1再进行判定即可。
代码
class Solution {
public:bool isUnique(string astr) {int n astr.size(); // 获取字符串的长度int c 0; // 使用一个整数c来表示出现过的字符情况for (int i 0; i n; i) {int t z - astr[i]; // 计算字符到 z 的距离if ((c t) 1) {// 如果对应位为1表示之前已经出现过相同的字符返回falsereturn false;} else {// 否则将对应位设为1表示该字符已经出现过c | (1 t);}}// 如果遍历完整个字符串没有发现重复字符返回truereturn true;}
};解释
c 是一个整数用来表示字符串中出现过的字符情况。这里用到了位运算通过将某一位设为1来表示某个字符是否出现过。t 计算了字符到 ‘z’ 的距离目的是在整数 c 中的相应位置标记字符是否出现过。(c t) 1 判断 c 中对应位是否为1如果为1说明之前已经有相同的字符出现返回false。c | (1 t) 将对应位设为1表示该字符已经出现过。
02.丢失的数字
题目链接https://leetcode.cn/problems/missing-number/
给定一个包含 [0, n] 中 n 个数的数组 nums 找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1
输入nums [3,0,1]
输出2
解释n 3因为有 3 个数字所以所有的数字都在范围 [0,3] 内。2 是丢失的数字因为它没有出现在 nums 中。示例 2
输入nums [0,1]
输出2
解释n 2因为有 2 个数字所以所有的数字都在范围 [0,2] 内。2 是丢失的数字因为它没有出现在 nums 中。示例 3
输入nums [9,6,4,2,3,5,7,0,1]
输出8
解释n 9因为有 9 个数字所以所有的数字都在范围 [0,9] 内。8 是丢失的数字因为它没有出现在 nums 中。示例 4
输入nums [0]
输出1
解释n 1因为有 1 个数字所以所有的数字都在范围 [0,1] 内。1 是丢失的数字因为它没有出现在 nums 中。提示
n nums.length1 n 1040 nums[i] nnums 中的所有数字都 独一无二
思路
同样我们这里可以使用哈希来进行标记但显然是需要额外的空间这里不使用额外空间还有其他的办法比如使用高斯求和公式求出前n项和再减去数组内数字的和或者使用异或运算我们使用先和数组中的每一个数异或再和数组长度每一位异或最终结果就是缺少的数
代码
class Solution {
public:int missingNumber(vectorint nums) {int nnums.size(),ret0;for(auto x:nums) ret^x;for(int i0;in;i) ret^i;return ret;}
};解释
ret 是用于保存异或结果的变量。第一次循环中对数组中的所有元素进行异或运算这样重复的元素会被抵消最终剩下的就是缺失的数字。第二次循环中对数组的下标和数组中的元素进行异或运算包括了所有可能的数字因为数组的下标范围是 [0, n]所以最终异或的结果即为缺失的数字。
03.两整数之和
题目链接https://leetcode.cn/problems/sum-of-two-integers/
给你两个整数 a 和 b 不使用 运算符 和 - 计算并返回两整数之和。
示例 1
输入a 1, b 2
输出3示例 2
输入a 2, b 3
输出5提示
-1000 a, b 1000
思路
这里我们需要知道位运算中的一种思想即无进位相加详细看下面代码即可
代码
class Solution {
public:int getSum(int a, int b) {while (b) {int t a ^ b; // 异或运算得到无进位的和b (a b) 1; // 与运算和左移1位得到进位a t; // 更新a为无进位和继续循环}return a; // 当进位为0时a即为最终的和}
};解释
a ^ b 执行异或运算得到无进位的和。(a b) 1 执行与运算和左移1位得到进位。因为只有在 a 和 b 的对应位都为1时才会产生进位。a t 更新 a 为无进位和继续循环直到进位为0。
04.只出现一次的数字 II
题目链接https://leetcode.cn/problems/single-number-ii/
给你一个整数数组 nums 除某个元素仅出现 一次 外其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
示例 1
输入nums [2,2,3,2]
输出3示例 2
输入nums [0,1,0,1,0,1,99]
输出99提示
1 nums.length 3 * 104-231 nums[i] 231 - 1nums 中除某个元素仅出现 一次 外其余每个元素都恰出现 三次
思路
外层循环遍历32位整数的每一位。内层循环遍历数组中的每个元素统计在当前位上出现的次数。对3取余得到只出现一次的元素在当前位上的值。将当前位上的值加到结果中。
代码
class Solution {
public:int singleNumber(vectorint nums) {int ret 0;for (int i 0; i 32; i) {int sum 0;for (auto x : nums) {// 统计数组中所有元素在当前位上的和if (x i 1) {sum;}}// 对3取余得到只出现一次的元素在当前位上的值sum % 3;// 将当前位上的值加到结果中if (sum) {ret | 1 i;}}return ret;}
};05.面试题 17.19. 消失的两个数字
题目链接https://leetcode.cn/problems/missing-two-lcci/
给定一个数组包含从 1 到 N 所有的整数但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗
以任意顺序返回这两个数字均可。
示例 1:
输入: [1]
输出: [2,3]示例 2:
输入: [2,3]
输出: [1,4]提示
nums.length 30000
思路
主要是通过两次异或操作来找到缺失的两个数。
第一次异或操作在第一次循环中首先对数组中的所有元素和[0, n2]范围内的所有数进行异或操作。这会得到一个结果 tmp其中包含了两个缺失的数的异或值。由于异或的性质重复的数都被抵消了而缺失的两个数的位上的值则保留了下来。
找到不同的位接着通过循环找到 tmp 二进制表示中的一个为1的位即找到两个缺失数的二进制表示中不同的位用 diff 表示。
第二次异或操作接下来再次循环数组和[0, n2]范围内的所有数根据 diff 的值将它们分为两组。一组中这个位上为1另一组中这个位上为0。这样就将问题转化为两个子问题分别找出每组中缺失的数。
返回结果最终返回的结果就是这两个缺失的数。将它们分别赋值给 a 和 b。
代码
class Solution {
public:vectorint missingTwo(vectorint nums) {int tmp 0;// 第一次异或将数组中的所有元素和[0, n2]范围内的所有数进行异或for (auto x : nums) {tmp ^ x;}for (int i 0; i nums.size() 2; i) {tmp ^ i;}int diff 0;// 找到两个缺失数字的二进制表示中不同的位while (1) {if (tmp diff 1) {break;}diff;}int a 0, b 0;// 第二次异或根据不同的位将数组分为两组for (auto x : nums) {if (x diff 1) {a ^ x;} else {b ^ x;}}for (int i 0; i nums.size() 2; i) {if (i diff 1) {a ^ i;} else {b ^ i;}}return {a, b};}
};
