算法思想之位运算(一)

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

算法介绍

位运算（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++)
快速幂	右移指数，逐位判断累乘

例题

位1的个数

题目链接

191. 位1的个数

题目描述

给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。

示例 1：

输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。

示例 2：

输入：n = 128
输出：1
解释：输入的二进制串 10000000 中，共有 1 个设置位。

示例 3：

输入：n = 2147483645
输出：30
解释：输入的二进制串 1111111111111111111111111111101 中，共有 30 个设置位。

提示：

• 1 <= n <= 231 - 1

进阶：
如果多次调用这个函数，你将如何优化你的算法？

算法思路

直接使用模板中消去最低位的1，直到变量为零，用一个变量计算次数即可。

代码实现

class Solution {
public:int hammingWeight(int n) {int ret = 0;while(n){n&=(n-1);ret++;}return ret;}
};

比特位计数

题目链接

338. 比特位计数

题目描述

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

提示：

• 0 <= n <= 105

进阶：

• 很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
• 你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

算法思路

遍历一遍数组，对于每个数，直接使用模板中消去最低位的1，直到变量为零，用一个变量计算次数即可。

代码实现

class Solution {
public:vector<int> countBits(int n) {vector<int> ans(n+1);for(int i = 0; i <= n; i++){int count = 0, num = i;while(num){num&=(num-1);count++;}ans[i] = count;}return ans;}
};    

只出现一次的数字

题目链接

136. 只出现一次的数字

题目描述

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：
输入：nums = [2,2,1]
输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：

输入：nums = [1]
输出：1

提示：

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• 除了某个元素只出现一次以外，其余每个元素均出现两次。

算法思路

1. 任何数和 0 做异或运算，结果仍然是原来的数，即 a^0=a。
2. 任何数和其自身做异或运算，结果是 0，即 a^a=0。
3. 异或运算满足交换律和结合律，即 a^b^a=b^a^a=b^(a^a)=b^0=b。

代码实现

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for(auto num : nums){ret ^= num;}return ret;}
};

只出现一次的数字 II

题目链接

137. 只出现一次的数字 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 - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

算法思路

设要找的数位 ret 。
由于整个数组中，需要找的元素只出现了一次，其余的数都出现的三次，因此我们可以根据所有数的某一个比特位的总和 %3 的结果，快速定位到 ret 的一个比特位上的值是0 还是 1 。
这样，我们通过 ret 的每一个比特位上的值，就可以将 ret 给还原出来。

代码实现

class Solution {
public:int singleNumber(vector<int>& nums) {int num = 0;for(int i = 0; i < 32; i++){int count = 0;for(auto n : nums){count += ((n>>i)&1);}if(count % 3)num |= (1<<i);}return num;}
};

只出现一次的数字 III

题目链接

260. 只出现一次的数字 III

题目描述

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]
输出：[-1,0]

示例 3：

输入：nums = [0,1]
输出：[1,0]

提示：

• 2 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
  除两个只出现一次的整数外，nums 中的其他数字都出现两次

算法思路

出现两次的数异或操作后会抵消，而两个不相等的数异或后的结果，必有一个比特位是为1的，我们根据这个比特位将所有数据分为两组。即可得出这两个数。

• 将所有数进行异或操作，异或后的结果中不为零的比特位即为区分点
• 通过找出的区分点，找出两个数。

代码实现

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {int num = 0;for(auto n : nums){num ^= n;}// 通过最低位的1将数据分为两组int l = (num==INT_MIN ? num : num&(-num));int sum1 = 0, sum2 = 0;for(auto n : nums){if(n & l)sum1^=n;elsesum2^=n;}return {sum1, sum2};}
};

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