位运算是利用二进制位特性解决问题的高效算法，核心通过「与（&）、或（|）、异或（^）、移位（<< / >>）」等基础操作，将时间/空间复杂度优化到极致（通常为O(n)O(n)O(n)时间、O(1)O(1)O(1)空间）。
它的应用场景覆盖“位计数”“找唯一数”“数值运算”“状态压缩”等核心问题，是算法面试中高频且易掌握的考点。本文将通过10道经典题目，拆解位运算在不同场景下的解题逻辑与代码实现。
一、汉明重量（统计二进制中1的个数）
题目描述：
输入一个无符号整数（二进制串形式），返回其二进制表达式中数字位数为1的个数（汉明重量）。
示例：
- 输入：
n = 00000000000000000000000000001011，输出：3 - 输入：
n = 11111111111111111111111111111101，输出：31
解题思路：
利用n & (n - 1)的核心特性：该操作会消去n二进制中最右边的1。循环执行该操作直到n为0，统计循环次数即为1的个数。
完整代码：
classSolution{public:inthammingWeight(intn){intcnt=0;while(n){n&=(n-1);cnt++;}returncnt;}};复杂度分析：
- 时间复杂度：O(k)O(k)O(k)，
k是二进制中1的个数（最坏O(32)O(32)O(32)，常数级）。 - 空间复杂度：O(1)O(1)O(1)，仅用常数级额外变量。
二、比特位计数
题目描述：
给定整数n，对0 ≤ i ≤ n的每个i，计算其二进制中1的个数，返回长度为n+1的结果数组。
示例：
- 输入：
n = 2，输出：[0,1,1] - 输入：
n = 5，输出：[0,1,1,2,1,2]
解题思路：
复用“汉明重量”的核心逻辑：遍历0~n的每个数，逐个统计二进制中1的个数，存入结果数组。
完整代码：
classSolution{public:vector<int>countBits(intn){vector<int>ret;intcnt=0;for(inti=0;i<=n;i++){inttmp=i;while(tmp){tmp&=(tmp-1);cnt++;}ret.push_back(cnt);cnt=0;}returnret;}};复杂度分析：
- 时间复杂度：O(n×k)O(n×k)O(n×k)，
k是单个数字二进制中1的个数（最坏O(32n)O(32n)O(32n)，仍为线性级）。 - 空间复杂度：O(1)O(1)O(1)，结果数组为必要输出，不计入额外空间。
三、汉明距离
题目描述：
两个整数的汉明距离是其二进制位不同的位置数目。给定x和y，返回它们的汉明距离。
示例：
- 输入：
x = 1, y = 4，输出：2（1:0001，4:0100，不同位有2个）
解题思路：
- 异或操作
x ^ y：结果中1的位置对应两个数二进制不同的位置，0对应相同位置。 - 统计异或结果中
1的个数（复用汉明重量逻辑），即为汉明距离。
完整代码：
classSolution{public:inthammingDistance(intx,inty){intn=x^y;intret=0;while(n!=0){n&=n-1;ret++;}returnret;}};复杂度分析：
- 时间复杂度：O(k)O(k)O(k)，
k是异或结果中1的个数（常数级）。 - 空间复杂度：O(1)O(1)O(1)，仅用常数级额外变量。
四、只出现一次的数字（其余出现两次）
题目描述：
给定非空整数数组，除某个元素只出现一次外，其余元素均出现两次。找出该元素（要求线性时间、不使用额外空间）。
示例：
- 输入：
nums = [2,2,1]，输出：1 - 输入：
nums = [4,1,2,1,2]，输出：4
解题思路：
利用异或的核心特性：
a ^ a = 0（相同数异或抵消）；a ^ 0 = a（与0异或保留自身）；- 异或满足交换律/结合律。
遍历数组，所有数异或的结果即为只出现一次的数。
完整代码：
classSolution{public:intsingleNumber(vector<int>&nums){intret=0;for(autox:nums){ret^=x;}returnret;}};复杂度分析：
- 时间复杂度：O(n)O(n)O(n)，遍历数组一次。
- 空间复杂度：O(1)O(1)O(1)，仅用常数级额外变量。
五、只出现一次的数字（其余出现三次）
题目描述：
给定整数数组，除某个元素只出现一次外，其余元素均出现三次。找出该元素（要求O(n)O(n)O(n)时间、O(1)O(1)O(1)空间）。
示例：
- 输入：
nums = [2,2,3,2]，输出：3 - 输入：
nums = [0,1,0,1,0,1,99]，输出：99
解题思路：
按二进制位统计：
- 遍历每一位（0~31位，覆盖int所有位）：
- 统计数组中所有数在该位上
1的总个数sum； - 若
sum % 3 = 1，说明唯一数在该位上是1（其余数出现三次，该位1的个数是3的倍数，抵消后剩余1）；
- 统计数组中所有数在该位上
- 逐位构建结果：将为1的位通过
ret |= 1 << i写入结果。
完整代码：
classSolution{public:intsingleNumber(vector<int>&nums){intret=0;for(inti=0;i<32;i++){intsum=0;for(autox:nums)if(((x>>i)&1)==1)sum++;sum%=3;if(sum==1)ret|=1<<i;}returnret;}};复杂度分析：
- 时间复杂度：O(32n)O(32n)O(32n)，遍历32位，每位遍历数组一次（仍为线性级O(n)O(n)O(n)）。
- 空间复杂度：O(1)O(1)O(1)，仅用常数级额外变量。
六、只出现一次的数字（两个唯一数）
题目描述：
给定整数数组，恰好两个元素只出现一次，其余元素均出现两次。找出这两个元素（要求O(n)O(n)O(n)时间、O(1)O(1)O(1)空间）。
示例：
- 输入：
nums = [1,2,1,3,2,5]，输出：[3,5]
解题思路：
- 全体异或：得到两个唯一数的异或和
xor_sum（其余数出现两次，异或抵消）。 - 找最低位1：
lowbit = xor_sum & (-xor_sum)，该位表示两个唯一数在该位上二进制不同。 - 分组异或：按
lowbit将数组分为两组（该位为0/1），每组内只有一个唯一数，其余数出现两次，分别异或得到结果。
⚠️ 注意：==优先级高于&，判断时需加括号。
完整代码：
classSolution{public:vector<int>singleNumber(vector<int>&nums){unsignedintxor_sum=0;for(autoc:nums){xor_sum^=c;}intlowbit=xor_sum&(-xor_sum);vector<int>ret(2);for(autoc:nums){if((lowbit&c)==0)// == 优先级高于 &，必须加括号ret[0]^=c;elseret[1]^=c;}returnret;}};复杂度分析：
- 时间复杂度：O(n)O(n)O(n)，两次遍历数组。
- 空间复杂度：O(1)O(1)O(1)，仅用常数级额外变量。
七、判定字符是否唯一
题目描述：
实现算法判断字符串astr的所有字符是否唯一（进阶：不使用额外数据结构）。
示例：
- 输入：
astr = "leetcode"，输出：false - 输入：
astr = "abc"，输出：true
解题思路：
状态压缩：用一个int（32位）的每一位表示对应字母（a-z）是否出现过：
- 若字符串长度>26，直接返回
false（a-z仅26个字母）。 - 遍历字符，计算偏移量
i = ch - 'a'：- 检查
(bitMap >> i) & 1，若为1说明字符重复； - 否则将
bitMap的第i位设为1（bitMap |= (1 << i)）。
- 检查
完整代码：
classSolution{public:boolisUnique(string astr){if(astr.size()>26)returnfalse;intbitMap=0;for(autoch:astr){inti=ch-'a';if((bitMap>>i)&1==1)returnfalse;bitMap|=(1<<i);}returntrue;}};复杂度分析：
- 时间复杂度：O(n)O(n)O(n)，遍历字符串一次（
n≤26，常数级）。 - 空间复杂度：O(1)O(1)O(1)，仅用一个int存储状态。
八、缺失的数字
题目描述：
给定包含[0, n]中n个数的数组nums，找出[0, n]范围内未出现的数。
示例：
- 输入：
nums = [3,0,1]，输出：2 - 输入：
nums = [0,1]，输出：2
解题思路：
复用异或特性：
- 将数组所有数异或，得到中间结果。
- 再将中间结果异或
0~n的所有数，最终结果即为缺失的数（出现两次的数抵消，缺失数仅异或一次）。
完整代码：
classSolution{public:intmissingNumber(vector<int>&nums){intret=0;for(autoch:nums)ret^=ch;for(inti=0;i<=nums.size();i++)ret^=i;returnret;}};复杂度分析：
- 时间复杂度：O(n)O(n)O(n)，两次遍历（数组+0~n）。
- 空间复杂度：O(1)O(1)O(1)，仅用常数级额外变量。
九、两整数之和
题目描述：
不使用+和-运算符，计算并返回两个整数a和b的和。
示例：
- 输入：
a = 1, b = 2，输出：3 - 输入：
a = -2, b = 3，输出：1
解题思路：
用位运算模拟加法：
- 异或
a ^ b：得到两数相加无进位的结果。 - 与运算后左移1位
(a & b) << 1：得到相加的进位值。 - 循环：将无进位结果作为新的
a，进位作为新的b，直到进位为0，此时a即为和。
完整代码：
classSolution{public:intgetSum(inta,intb){while(b){intx=a^b;intcarry=(a&b)<<1;a=x;b=carry;}returna;}};复杂度分析：
- 时间复杂度：O(k)O(k)O(k)，
k是二进制位数（常数级）。 - 空间复杂度：O(1)O(1)O(1)，仅用常数级额外变量。
十、丢失的两个数字
题目描述：
给定数组包含1~N的整数（缺两个数），在O(n)O(n)O(n)时间、O(1)O(1)O(1)空间内找出这两个数。
示例：
- 输入：
nums = [1]，输出：[2,3] - 输入：
nums = [2,3]，输出：[1,4]
解题思路：
结合“两个唯一数”和“缺失数字”的逻辑：
- 全体异或：数组所有数异或
1~n+2（n是数组长度），得到两个缺失数的异或和ret。 - 找最低位1：
lowbit = ret & (-ret)，按该位分组。 - 分组异或：每组内分别异或数组元素和
1~n+2的数，得到两个缺失数。
完整代码：
classSolution{public:vector<int>missingTwo(vector<int>&nums){intret=0;for(autox:nums)ret^=x;for(inti=1;i<=nums.size()+2;i++)ret^=i;intlowbit=ret&(-ret);vector<int>ans(2);for(autox:nums)if((lowbit&x)==0)ans[0]^=x;elseans[1]^=x;for(inti=1;i<=nums.size()+2;i++)if((lowbit&i)==0)ans[0]^=i;elseans[1]^=i;returnans;}};复杂度分析：
- 时间复杂度：O(n)O(n)O(n)，多次遍历数组/数字范围，均为线性级。
- 空间复杂度：O(1)O(1)O(1)，仅用常数级额外变量。
