位运算篇——位海拾遗，探秘数字世界的亚特兰蒂斯（1）

在这里插入图片描述

前言

在计算机科学的浩瀚疆域中，位运算如同深海中的珍珠，虽隐匿于基本操作之中，却闪耀着无可比拟的效率与简洁之美。它以“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 思路讲解：

异或相同为0，相异为1，实际上就是不进位的加法。

与运算都为1时结果才为1，反之则都为0，实际上就是计算进位。

因此在处理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;}
};