算法思想之位运算(二)

欢迎拜访：雾里看山-CSDN博客
本篇主题：算法思想之位运算(二)
发布时间：2025.4.13
隶属专栏：算法

滑动窗口算法介绍

位运算（Bit Manipulation）是算法中的高效技巧，通过直接操作二进制位实现快速计算和优化存储

六大基础位运算符

运算符	符号	描述	示例
按位与	&	两数二进制位同为1时结果为1	5 & 3 → 1 (101 & 011 = 001)
按位或	|	任一位为1时结果为1	5 | 3→7 (101 | 011 = 111)
按位异或	^	两数位不同时结果为1 ，无进位相加	5 ^ 3 → 6 (101 ^ 011 = 110)
按位取反	~	0变1，1变0	~5 → -6（补码表示）
左移	<<	左移指定位数，低位补0	5 << 1 → 10 (101→1010)
右移	>>	右移指定位数，高位补符号位（算术右移）	-5 >> 1 → -3

常用模板总结

功能	代码模板
判断奇偶	x & 1 → 1为奇，0为偶
取最低位的1	x & (-x)
消去最低位的1	x & (x - 1)
异或交换变量	a ^= b; b ^= a; a ^= b;
生成所有子集	for (mask = 0; mask < (1 << n); mask++)
快速幂	右移指数，逐位判断累乘

例题

判定字符是否唯一

题目链接

面试题 01.01. 判定字符是否唯一

题目描述

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：

输入: s = “leetcode”
输出: false

示例 2：

输入: s = “abc”
输出: true

限制：

• 0 <= len(s) <= 100
• s[i]仅包含小写字母
• 如果你不使用额外的数据结构，会很加分。

算法思路

利⽤位图的思想，每一个比特位代表一个字符，一个 int 类型的变量的 32 位足够表示所有的小写字母。比特位里面如果是 0 ，表示这个字符没有出现过。比特位里面的值是 1 ，表示该字符出现过。
那么我们就可以用一个整数来充当哈希表。

代码实现

class Solution {
public:bool isUnique(string astr) {if(astr.size() > 26)return false;int num = 0;for(auto c : astr){if(num>>(c-'a')&1)return false;elsenum |= 1<<(c-'a');}return true;}
};

汉明距离

题目链接

461. 汉明距离

题目描述

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。

示例 2：

输入：x = 3, y = 1
输出：1

提示：

• 0 <= x, y <= 231 - 1

算法思路

对两个数进行异或操作，异或后1的个数，即为汉明距离。直接使用模板中消去最低位的1，直到变量为零，用一个变量计算次数即可。

代码实现

class Solution {
public:int hammingDistance(int x, int y) {int ret = 0, n = x ^ y;while(n){n&=(n-1);ret++;}return ret;}
};

丢失的数字

题目链接

268. 丢失的数字

题目描述

给定一个包含 [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 中。

提示：

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• nums 中的所有数字都 独一无二

进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

算法思路

设数组的大小为 n ，那么缺失之前的数就是 [0, n] ，数组中是在 [0, n] 中缺失一个数形成的序列。
如果我们把数组中的所有数，以及 [0, n] 中的所有数全部异或在一起，那么根据异或运算的消消乐规律，最终的异或结果应该就是缺失的数。

代码实现

class Solution {
public:int missingNumber(vector<int>& nums) {int n = nums.size();int ret = 0;for(auto num : nums)ret^=num;for(int i = 0; i <= n; i++)ret^=i;return ret;}
};

两整数之和

题目链接

371. 两整数之和

题目描述

给你两个整数 a 和 b ，不使用 运算符 + 和 -，计算并返回两整数之和。

示例 1：

输入：a = 1, b = 2
输出：3

示例 2：

输入：a = 2, b = 3
输出：5
提示：

• -1000 <= a, b <= 1000

算法思路

• 异或 ^ 运算本质是无进位加法；
• 按位与 & 操作能够得到进位；
• 然后一直循环进行，直到进位变成 0 为止。

代码实现

class Solution {
public:int getSum(int a, int b) {int sum = 0, carry = 0;do{sum = a ^ b;// 无进位相加carry = (a&b)<<1;// 进位操作a = sum;b = carry;}while(carry != 0);return sum;}
};

消失的两个数字

题目链接

面试题 17.19. 消失的两个数字

题目描述

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

示例 1：

输入：[1]
输出：[2,3]

示例 2：

输入：[2,3]
输出：[1,4]

提示：

• nums.length <= 30000

算法思路

本题就是 268. 丢失的数字 + 260. 只出现⼀次的数字 III 组合起来的题。
先将数组中的数和 [1, n + 2] 区间内的所有数异或在一起，问题就变成了：有两个数出现了一次，其余所有的数出现了两次。进而变成了 260. 只出现⼀次的数字 III 这道题。

代码实现

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int n = nums.size() + 2;int sum = 0;for(auto num : nums)sum ^= num;for(int i = 1; i <= n; i++)sum ^= i;int low = (sum==INT_MIN ? sum : sum&(-sum));// 取出最低位int ans1 = 0, ans2 = 0;for(auto num : nums){if(num & low)ans1^=num;elseans2^=num;}for(int i = 1; i <= n; i++){if(i & low)ans1^=i;else    ans2^=i;}return {ans1, ans2};}
};

⚠️ 写在最后：以上内容是我在学习以后得一些总结和概括，如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流！！！