前言
在计算机科学的浩瀚疆域中，位运算如同深海中的珍珠，虽隐匿于基本操作之中，却闪耀着无可比拟的效率与简洁之美。它以“0”和“1”组成的语言为基础，通过简单的逻辑实现复杂的功能，被广泛应用于数据处理、算法优化和硬件设计等领域。本文将带领读者走进位运算的世界，揭示其核心概念、常用操作及实际应用，感受数字海洋中的奇妙逻辑。
一、位运算的基本概念
位运算是直接对二进制位进行操作的一组算法。常见的位运算包括以下几种：
按位与（&）
规则：两位均为1，结果为1，否则为0。
作用：用于掩码操作，保留指定位上的值。
按位或（|）
规则：任一位为1，结果为1，否则为0。
作用：用于设置某些位为1。
按位异或（^）
规则：两位相异，结果为1，否则为0。
作用：可实现位翻转与加密解密操作。
按位取反（~）
规则：对每个位进行取反操作。
作用：用于快速求补数等操作。
左移（<<）与右移（>>）
左移：将所有位向左移动指定位置，右侧补0。
右移：分为算术右移（保留符号位）与逻辑右移（补0）。
作用：快速实现乘除2的幂运算。
二. 典型算法解析
-
判断奇偶性
算法：n & 1
原理：二进制中最低位为1表示奇数，为0表示偶数。 -
交换两个数
算法：
a = a ^ b;
b = a ^ b;
a = a ^ b;
原理：通过异或操作使两个数交换，无需借助额外变量。
-
清除最低位的1
算法：n = n & (n - 1)
原理：n - 1会将最低位的1及其右边全部取反，与n按位与即可清除最低位的1。 -
统计二进制中1的个数
算法：
int count = 0;
while (n) {
n = n & (n - 1);
count++;
}
原理：每次清除一个最低位的1，直到n为0。
下面我们将结合具体题目进行练习。
三. 判断字符串是否唯一
3.1 题目链接：https://leetcode.cn/problems/is-unique-lcci/description/
3.2 题目分析：
题目要求判断字符串是否唯一，即要求字符串内不能存在重复字符。
该题方法多样，且题目特别说明，如果不使用数据结构，会很加分，因此可以考虑使用位运算。
3.3 思路讲解：
位运算：
众所周知，一个字节有8个比特位，而一个int类型的数据有4个字节，32个比特位，恰好可涵盖26个字母，可考虑使用位图映射解决。
⽐特位⾥⾯如果是 0 ，表⽰这个字符没有出现过。⽐特位⾥⾯的值是 1 ，
表⽰该字符出现过。
那么我们就可以⽤⼀个「整数」来充当「哈希表」。
3.4 代码实现：
class Solution {
public:
bool isUnique(string astr) {
int bitmap=0;//采用位图记录
if(astr.size()>26)
{
return false;
}//鸽巢原理
for(auto e:astr)
{
int i=e-'a';//移动位数
if((bitmap>>i&1)==1)
{
return false;
}//说明该字符已经出现过
bitmap|=1<<i;//记录入位图
}
return true;
}
};
四. 丢失的数字
4.1 题目链接：https://leetcode.cn/problems/missing-number/description/
4.2 题目分析：
数组内有n个数，但缺失了一个数字，完整范围应该为[0,n]，题目要求我们找出该数字。
4.3 思路讲解：
该题方法多样，例如，我们可以通过令sum1记录[0,n]的和，sum2记录数组内所有元素的和，sum1-sum2即为所求。
但由于本篇重点为位运算，因此我们重点讲解位运算算法。
位运算：
- 异或的核心在于相同为0，相异为1，且一连串元素异或时，最终结果与异或顺序无关。
- 因此可以令target先与数组内各个元素异或，再与[0,n]内元素逐个异或，由于除了缺失的数字外，其他数字均出现了两次，因此最终结果即为消失的数字
4.4 代码实现：
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n=nums.size();
int target=0;
for(auto e:nums)
{
target^=e;
}//与数组内元素逐个异或
for(int i=0;i<=n;i++)
{
target^=i;
}//与[0,n]内元素逐个异或
return target;
}
};
五. 两整数之和
5.1 题目链接：https://leetcode.cn/problems/sum-of-two-integers/description/
5.2 题目分析：
题目要求计算两个整数的和，但要求不可以使用+和-。
注意：当我们在做笔试题或者其他黑盒测试时，即使我们直接return a+b，仍然可以成功通过。
5.3 思路讲解：
因此在处理a+b时，我们只需要先异或求出不进位的和，再逐位&求出进位，最终结果即为a+b。
5.4 代码实现：
class Solution {
public:
int getSum(int a, int b) {
while(b!=0)
{
int temp=a^b;//异或是不做进位的加法
unsigned int carry=(a&b)<<1;//左移求进位
a=temp;
b=carry;
}
return a;
}
};
小结：
本篇关于位运算的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！