【算法从零到千】【32-41】位运算（详细讲解+题目运用）
1. 基础位运算
与
&：有0就是0。或
|：有1就是1。非
~：按位取反。异或
^：相同为0，相异为1（可以理解为无进位相加）。2. 特定位的检查与修改
检查第 x 位是 0 还是 1
公式：
(n >> x) & 1解释：将 n 右移 x 位，再与 1 进行与运算。结果为 1 则原位为 1，为 0 则原位为 0。
将第 x 位修改为 1
公式：
n | (1 << x)解释：构造一个只有第 x 位为 1 的数（
1 << x），与原数进行或运算。将第 x 位修改为 0
公式：
n & (~(1 << x))解释：将
1 << x取反，得到一个除了第 x 位是 0 其余全是 1 的面具，与原数进行与运算，从而清零第 x 位。3. 位图 (Bitmap) 思想
利用整数数组来模拟位数组。
应用场景：状态压缩、布隆过滤器、海量数据处理（如 int 数组的每个 bit 可以表示一个数据的存在与否）。
4. 常用技巧公式
提取最右侧的 1 (
lowbit)
公式：
n & -n作用：得到 n 中最右边那个 1 及其右边的所有 0 组成的数。常用于树状数组 (Fenwick Tree) 或统计二进制中 1 的个数。
干掉最右侧的 1
公式：
n & (n - 1)作用：将 n 的最右边那个 1 变成 0。常用于判断一个数是否是 2 的幂（如果是，则
n & (n-1) == 0），或用于统计二进制中 1 的个数。5. 运算优先级
位运算的优先级普遍较低且容易混淆。
建议：在实际编程中，能加括号就加括号，避免因优先级问题导致逻辑错误。
6. 异或 (XOR) 运算律
a ^ 0 = a（0 是异或的单位元）
a ^ a = 0（自己异或自己等于 0，常用于“消消乐”）
a ^ b ^ c = a ^ (b ^ c)（满足结合律）特性：交换律。
1.判断字符是否唯一
面试题 01.01. 判定字符是否唯一
实现一个算法，确定一个字符串
s的所有字符是否全都不同。class Solution { public: bool isUnique(string astr) { if(astr.size()>26) return false;//鸽巢原理 int bitMap=0; for(auto& e:astr) { int i=e-'a'; if(((bitMap>>i)&1)==1)return false; else bitMap|=(1<<i); } return true; } };2.只出现一次的数字（系列）
136. 只出现一次的数字
https://leetcode.cn/problems/single-number/
给你一个 非空 整数数组
nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
class Solution { public: int singleNumber(vector<int>& nums) { int i=0; for(auto& e:nums) { i=i^e; } return i; } };137. 只出现一次的数字 II
https://leetcode.cn/problems/single-number-ii/
给你一个整数数组
nums，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题
class Solution { public: int singleNumber(vector<int>& nums) { int bitMap=0; for(int i=0;i<32;i++) { int sum=0; for(auto& e:nums) { if(((e>>i)&1)==1) sum++; } sum%=3; if(sum==1) bitMap=bitMap|(1<<i); } return Map; } };260. 只出现一次的数字 III
https://leetcode.cn/problems/single-number-iii/
给你一个整数数组
nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题
class Solution { public: int getfirst1(int i) { int index=0; while((i&1)==0&&index<32) { i>>=1; index++; } return index; } vector<int> singleNumber(vector<int>& nums) { if(nums.size()==2) return nums; int i=0; for(auto& e:nums) { i^=e; //x1^x2 } int x1=0,x2=0; int index=getfirst1(i); for(auto& ch:nums) { if(((ch>>index)&1)==0) x1^=ch; else x2^=ch; } return {x1,x2}; } };3.位1的个数
LCR 133. 位 1 的个数
https://leetcode.cn/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。
class Solution { public: int hammingWeight(uint32_t n) { int count=0,index=0; while(index<32) { if(n&1==1)count++; n>>=1; index++; } return count; } };4.比特位计数
LCR 003. 比特位计数
https://leetcode.cn/problems/w3tCBm/
给定一个非负整数
n，请计算0到n之间的每个数字的二进制表示中 1 的个数，并输出一个数组class Solution { public: int hammingWeight(int n) { int count=0,index=0; while(index<32) { if((n&1)==1)count++; n>>=1; index++; } return count; } vector<int> countBits(int n) { int i=0;vector<int> v;; while(i<=n) { v.emplace_back(hammingWeight(i++)); } return v; } };5.汉明距离
461. 汉明距离
https://leetcode.cn/problems/hamming-distance/
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数
x和y，计算并返回它们之间的汉明距离。class Solution { public: int hammingDistance(int x, int y) { int count=0,index=0; while(index<32) { if((x&1)!=(y&1)) count++; index++;x>>=1;y>>=1; } return count; } };6.丢失的数字
268. 丢失的数字
https://leetcode.cn/problems/missing-number/
给定一个包含
[0, n]中n个数的数组nums，找出[0, n]这个范围内没有出现在数组中的那个数class Solution { public: int missingNumber(vector<int>& nums) { int sum=0; for(auto e:nums)sum^=e; for(int i=0;i<=nums.size();i++)sum^=i; return sum; } };7.两整数之和
371. 两整数之和
https://leetcode.cn/problems/sum-of-two-integers/
给你两个整数
a和b，不使用 运算符+和-，计算并返回两整数之和。
class Solution { public: int getSum(int a, int b) { u_int c=1,d; while(c!=0) { c=a&b;c<<=1; d=a^b; a=c;b=d; } return d; } };8.消失的两个数字
面试题 17.19. 消失的两个数字
https://leetcode.cn/problems/missing-two-lcci/
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
class Solution { public: int getfirst1(int i) { int index=0; while((i&1)==0&&index<32) { index++; i>>=1; } return index; } vector<int> missingTwo(vector<int>& nums) { int ch=0; for(int i=1;i<=nums.size()+2;i++) { ch^=i; } for(auto& e:nums) { ch^=e; } //得到两个数字的异或 int f1=getfirst1(ch); int x1=0,x2=0; for(auto& e:nums) { if(((e>>f1)&1)==0) x1^=e; else x2^=e; } for (int i = 1; i <=nums.size()+2 ; i++) { if (((i>>f1)&1) == 0) x1 ^= i; else x2 ^= i; } return{x1,x2}; } };