【算法】位运算看这一篇就够了：操作符、技巧与算法实战

位运算算法详解

位运算是一种直接对整数在内存中的二进制位进行操作的低级运算，由于计算机底层就是二进制，位运算的效率非常高。

一、基础位运算操作符

二、常用位运算技巧

1. 判断奇偶性

// 常规方法boolisOdd(intn){returnn%2==1;}// 位运算方法：判断最低位boolisOdd(intn){returnn&1;// 如果最后一位是1，则是奇数}

2. 交换两个数（不使用临时变量）

voidswap(int&a,int&b){a=a^b;b=a^b;// b = (a^b)^b = aa=a^b;// a = (a^b)^a = b}

3. 获取二进制中第k位

intgetBit(intn,intk){return(n>>k)&1;// 右移k位后取最低位}

4. 将第k位设置为1

intsetBit(intn,intk){returnn|(1<<k);// 将1左移k位后按位或}

5. 将第k位设置为0

intclearBit(intn,intk){returnn&~(1<<k);// 将1左移k位后取反，再按位与}

6. 翻转第k位

inttoggleBit(intn,intk){returnn^(1<<k);// 异或1实现翻转}

7. 统计二进制中1的个数

// 方法1：逐位判断intcountOnes(intn){intcount=0;while(n){count+=n&1;n>>=1;}returncount;}// 方法2：Brian Kernighan算法（效率更高）intcountOnes(intn){intcount=0;while(n){n&=(n-1);// 消除最低位的1count++;}returncount;}

三、常见位运算算法题

1. 判断一个数是否是2的幂

boolisPowerOfTwo(intn){if(n<=0)returnfalse;return(n&(n-1))==0;// 2的幂只有一个1，消除后为0}

2. 找出只出现一次的数字（其他数字都出现两次）

intsingleNumber(vector<int>&nums){intresult=0;for(intnum:nums){result^=num;// 异或运算：相同为0，不同为1}returnresult;}

3. 找出两个只出现一次的数字

vector<int>singleNumber(vector<int>&nums){// 先对所有数异或，得到两个目标数的异或结果intxorResult=0;for(intnum:nums){xorResult^=num;}// 找到异或结果中最低位的1（用于分组）intmask=xorResult&(-xorResult);// 获取最低位的1// 根据该位分组异或inta=0,b=0;for(intnum:nums){if(num&mask){a^=num;}else{b^=num;}}return{a,b};}

4. 计算两个整数的和（不使用+和-）

intgetSum(inta,intb){while(b!=0){intcarry=(a&b)<<1;// 进位a=a^b;// 不进位加法b=carry;// 循环处理进位}returna;}

5. 子集枚举

vector<vector<int>>subsets(vector<int>&nums){vector<vector<int>>result;intn=nums.size();// 用二进制位表示每个元素选或不选for(intmask=0;mask<(1<<n);mask++){vector<int>subset;for(inti=0;i<n;i++){if(mask&(1<<i)){// 检查第i位是否为1subset.push_back(nums[i]);}}result.push_back(subset);}returnresult;}

四、位运算的应用场景

1. 状态压缩：用整数的二进制位表示状态，节省空间
2. 权限管理：用不同位表示不同权限
3. 加密解密：异或运算常用于简单的加密
4. 图形学：颜色值的RGB分量操作
5. 性能优化：替代乘除法、取模等操作

五、注意事项

1. 优先级问题：位运算符优先级低于比较运算符，使用时建议加括号
2. 有符号数移位：右移对于负数，符号位处理取决于编译器
3. 溢出风险：左移可能改变符号位或导致溢出
4. 可读性：适当使用，必要时添加注释

位运算虽然看起来复杂，但掌握后能写出更高效的代码，特别是在算法竞赛和底层开发中非常有用。

六、实战（含题目链接）

判断字符是否唯⼀（easy）
丢失的数字（easy）
两整数之和（medium）
只出现⼀次的数字 II（medium）
面试题 17.19. 消失的两个数字（hard）