目录位运算算法详解一、基础位运算操作符二、常用位运算技巧1. 判断奇偶性2. 交换两个数不使用临时变量3. 获取二进制中第k位4. 将第k位设置为15. 将第k位设置为06. 翻转第k位7. 统计二进制中1的个数三、常见位运算算法题1. 判断一个数是否是2的幂2. 找出只出现一次的数字其他数字都出现两次3. 找出两个只出现一次的数字4. 计算两个整数的和不使用和-5. 子集枚举四、位运算的应用场景五、注意事项六、实战含题目链接位运算算法详解位运算是一种直接对整数在内存中的二进制位进行操作的低级运算由于计算机底层就是二进制位运算的效率非常高。一、基础位运算操作符操作符名称规则示例按位与两个位都是1时结果为15 3 1(0101 0011 0001)|按位或至少有一个1时结果为15 | 3 7(0101 | 0011 0111)^按位异或两个位不同时结果为15 ^ 3 6(0101 ^ 0011 0110)~按位取反0变11变0~5 -6(0101 - 1010)左移左移n位右边补05 1 10(0101 - 1010)右移右移n位正数左边补05 1 2(0101 - 0010)二、常用位运算技巧1. 判断奇偶性// 常规方法boolisOdd(intn){returnn%21;}// 位运算方法判断最低位boolisOdd(intn){returnn1;// 如果最后一位是1则是奇数}2. 交换两个数不使用临时变量voidswap(inta,intb){aa^b;ba^b;// b (a^b)^b aaa^b;// a (a^b)^a b}3. 获取二进制中第k位intgetBit(intn,intk){return(nk)1;// 右移k位后取最低位}4. 将第k位设置为1intsetBit(intn,intk){returnn|(1k);// 将1左移k位后按位或}5. 将第k位设置为0intclearBit(intn,intk){returnn~(1k);// 将1左移k位后取反再按位与}6. 翻转第k位inttoggleBit(intn,intk){returnn^(1k);// 异或1实现翻转}7. 统计二进制中1的个数// 方法1逐位判断intcountOnes(intn){intcount0;while(n){countn1;n1;}returncount;}// 方法2Brian Kernighan算法效率更高intcountOnes(intn){intcount0;while(n){n(n-1);// 消除最低位的1count;}returncount;}三、常见位运算算法题1. 判断一个数是否是2的幂boolisPowerOfTwo(intn){if(n0)returnfalse;return(n(n-1))0;// 2的幂只有一个1消除后为0}2. 找出只出现一次的数字其他数字都出现两次intsingleNumber(vectorintnums){intresult0;for(intnum:nums){result^num;// 异或运算相同为0不同为1}returnresult;}3. 找出两个只出现一次的数字vectorintsingleNumber(vectorintnums){// 先对所有数异或得到两个目标数的异或结果intxorResult0;for(intnum:nums){xorResult^num;}// 找到异或结果中最低位的1用于分组intmaskxorResult(-xorResult);// 获取最低位的1// 根据该位分组异或inta0,b0;for(intnum:nums){if(nummask){a^num;}else{b^num;}}return{a,b};}4. 计算两个整数的和不使用和-intgetSum(inta,intb){while(b!0){intcarry(ab)1;// 进位aa^b;// 不进位加法bcarry;// 循环处理进位}returna;}5. 子集枚举vectorvectorintsubsets(vectorintnums){vectorvectorintresult;intnnums.size();// 用二进制位表示每个元素选或不选for(intmask0;mask(1n);mask){vectorintsubset;for(inti0;in;i){if(mask(1i)){// 检查第i位是否为1subset.push_back(nums[i]);}}result.push_back(subset);}returnresult;}四、位运算的应用场景状态压缩用整数的二进制位表示状态节省空间权限管理用不同位表示不同权限加密解密异或运算常用于简单的加密图形学颜色值的RGB分量操作性能优化替代乘除法、取模等操作五、注意事项优先级问题位运算符优先级低于比较运算符使用时建议加括号有符号数移位右移对于负数符号位处理取决于编译器溢出风险左移可能改变符号位或导致溢出可读性适当使用必要时添加注释位运算虽然看起来复杂但掌握后能写出更高效的代码特别是在算法竞赛和底层开发中非常有用。六、实战含题目链接判断字符是否唯⼀easy丢失的数字easy两整数之和medium只出现⼀次的数字 IImedium面试题 17.19. 消失的两个数字hard