位运算这玩意儿很多写了几年业务代码的人对它的印象可能还停留在“面试会考”“竞赛炫技”的层面。我自己以前也一样平时能用除法绝不用移位能用临时变量绝不写异或交换总觉得位运算读起来费劲、写起来容易出岔子。直到参与过几个对性能极其敏感的场景比如嵌入式控制逻辑、大规模布隆过滤器的实现、以及状态压缩的动态规划才彻底改观位运算不是花拳绣脚而是一把能直接捅到硬件层面的螺丝刀。这篇“位运算技巧总结”不会只堆一堆奇技淫巧而是把实际开发里真正高频、可复用、能推导的位运算技巧拆开来讲每个技巧为什么成立、底层在算什么、有什么边界条件、什么时候不该用它。适合算法竞赛选手、底层开发、嵌入式工程师以及所有想把代码性能再挤一挤的同学。我会把代码示例和踩坑记录一起放出来希望能让你少走点弯路。1. 位运算的基础六个运算符与计算机的“补码世界观”1.1 为什么说位运算是性能问题的最终解很多人觉得位运算就是“快那么一点点”其实不止。它最大的优势不只是速度快而是无分支、无内存访问、单条指令完成操作。CPU处理一条加法指令和一条按位与指令在现代处理器上的延迟差异可能只有一两个周期但关键在于位运算不会触发分支预测失败不会依赖内存缓存不会产生复杂的依赖链。举个最典型的例子判断一个整数是奇数还是偶数。写成n % 2编译器通常能优化成n 1但那是开启优化之后的结果。在解释型语言里比如早期的Python环境或者在优化等级为O0的调试构建里取模运算仍然会走除法流程而除法在CPU里是一条比较昂贵的运算。换成n 1后本质上就是拿一个开关去测最低位1代表奇数0代表偶数。这不仅仅是快慢问题而是让代码直接对应硬件的基本操作。还有一个更实际的价值位运算是天然并行的。32位整数上的一次与、或、异或操作相当于同时操作了32个独立开关。这种特性被大量用在权限系统、状态标志位、图形学的颜色混合里。你要是能养成“用位运算去批量处理布尔集合”的思维习惯很多问题的代码量会直接缩短一个量级。1.2 六个基础运算符功能速查先别急着看技巧把六个基础运算符的“性格”摸清楚后面所有技巧都是它们组合出来的。我整理了一个最常用的速查表建议新同学把它当小抄存在笔记里运算符名称运算规则记忆要点按位与两位都为1时结果才为1核心是“保留”和“清零”按位或两位至少一个为1时结果为1^按位异或两位不同为1、相同为0核心是“翻转”和“抵消”~按位取反0变1、1变0和对某个数加1联动见补码左移所有位左移低位补0等价于乘以2的幂右移所有位右移高位补符号位或0等价于除以2的幂细节看符号这个表中最容易被低估的是异或。a ^ a等于0a ^ 0等于a这两条性质几乎承包了后面所有“消除成对元素”的玩法。按位与则承包了“掩码”类操作用一个二进制串去掐住某些位不放剩下的位全部清零。1.3 补码是你理解一切位运算的前提如果你只用无符号整数做题位运算很简单但实际编码里到处都是int、有符号数、负数。这时候绕不开的坎就是补码。先说结论在绝大多数主流架构和语言里整数是以补码形式存储的。正数的补码就是它本身的二进制负数的补码是“原码取反再加一”。比如-8在八位二进制里表示为11111000它就是800001000取反成11110111再加一得到的11111000。为什么这么设计因为补码让加减法统一成了加法电路x - y可以直接算成x (~y 1)。CPU不需要为减法单独设计一套电路省了至少一半的硬件逻辑。这个设计带来一个很重要的推论-x在代码层面等价于(~x) 1。这个推论是很多经典位运算技巧的源头比如后面要讲的lowbitx (-x)。看到负数不要去想“数学里的负号”而是要想“按位取反再加一”一切就通顺了。还有一点必须注意右移运算在有符号数和无符号数上行为不同。无符号数右移是逻辑右移高位补0有符号数在主流程编译器里是算术右移高位补符号位。Java里用表示无符号右移C/C里对无符号数直接就是逻辑右移。这个区别在负数场景下会直接改变结果后面避坑部分我会专门展开。2. 高频技巧实操从判断奇偶到定点操作2.1 奇偶判断与取模n 1的边界判断奇偶用n 1是最经典的位运算入门操作if (n 1) { // 奇数 } else { // 偶数 }原理一句话任何整数的二进制最低位是1就是奇数是0就是偶数。在补码体系下负数的最低语义和正数一样所以(-3) 1的结果也是1判断为奇数数学上完全正确。但这里有两个坑。第一个是运算符优先级的优先级高于位运算所以如果你写if ((n 1) 0)括号一定不能省。不加括号编译器会理解成n (1 0)也就是n 0恒等于0条件永远不成立。这种bug隐蔽到能让你排查半小时结果就是缺了一对括号。第二个坑是“取模能不能用与代替”。x (2^n - 1)等价于x % (2^n)但前提是x是非负数。以x 7, mod 4为例7 3 37 % 4 3没问题。可如果x -7结果就完全不同了-7 3在补码下算出来是1而-7 % 4按C标准是-3按Python则是1。也就是说负数场景下位运算取模和数学取模并不等同做底层代码时千万别想当然。2.2 异或交换变量原理很美使用很谨慎用异或交换两个整数是位运算教程里最常出现的“表演项目”a ^ b; b ^ a; a ^ b;我们来逐步验证。设初始时x a, y b。第一步执行a a ^ b此时a里存的是“两个数的差异信息”第二步执行b a ^ b (a ^ b) ^ b a因为b ^ b 0异或就完成了消去第三步执行a a ^ b (a ^ b) ^ a b。三步之后a和b完成交换。这个技巧的数学内核是异或的三大性质交换律、结合律、以及x ^ x 0的自反性。它让我第一次意识到“一个数值可以同时承载两个对象的信息差”这个眼光对理解布隆过滤器、纠错码、RAID磁盘阵列的奇偶校验都很有帮助。不过我必须泼一盆冷水实际生产代码里别这么写交换。你换成临时变量tmp a; a b; b tmp编译器在开启优化后生成的汇编代码基本一样甚至更优。而且异或交换有个致命边界如果a和b指向同一块内存比如数组里swap(arr[i], arr[i])第一步后值变成0后面两步直接把数组元素清零了。这种bug非常难查。我把异或交换定位为“思维训练题”而不是工程推荐做法。2.3 乘除2的幂移位运算与溢出陷阱x n等价于x * 2^nx n等价于x / 2^n正数场景。这个技巧在底层代码里出现频率高得惊人尤其是内存对齐、像素计算、哈希扩容等场景// 数组扩容为原来的2倍 new_capacity old_capacity 1; // 计算二分中位数防止加法溢出 mid left ((right - left) 1);这里有个值得展开的点为什么二分用(left right) 1而不直接写(left right) / 2除了除法慢更重要的原因是left right可能溢出有符号整数。一旦溢出结果变负数除出来完全不对。改用left ((right - left) 1)两个正数的差值不会溢出中间结果就安全多了。这是我在阅读开源二分实现时学到的后来自己写代码再也没踩过溢出坑。右移代替除以2在正数上没问题可一旦遇到负数就要注意算术右移是“向下取整”而C语言整数除法是“向零取整”。-3 1的结果是-2而-3 / 2的结果是-1。很多从C/C代码移植到Java、或者跨语言重写算法的人会在这里莫名其妙多一个数的偏差根源就是这个细微差别。2.4 判断2的幂与清除最低位的1判断一个正整数n是不是2的幂最优雅的写法bool isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }关键在于理解n (n - 1)的作用它会清除二进制里最低位的那个1。比如n 12二进制是1100n - 1 11二进制是1011与运算后得到1000也就是8原来的最低位1被清掉了。为什么能达到这个效果因为n - 1会让最低位的1变成0同时把更低位的所有0全部变成1。用生活类比减法像在剥洋葱从最底层开始借位剥到第一个非零位才停。与运算再把高位部分原样保留、低位部分清零。如果一个数只有一个1也就是2的幂清除之后自然变成0。顺带说一句n (n - 1)这个操作本身就是极其常用的工具它同时也是统计二进制里1个数的核心组件后面我还会用到。2.5 二进制的定点置一、清零与翻转在实际开发里最常用的二进制位操作其实是“对某个指定bit进行操作”。这三个套路必须刻进肌肉记忆// 将第k位置为1 x | (1 k); // 将第k位清为0 x ~(1 k); // 将第k位翻转 x ^ (1 k); // 读取第k位是0还是1 int bit (x k) 1;置1用的是或运算的“强推”能力清零用的是与运算加取反掩码翻转用的是异或的“拨动开关”能力。三个场景对应的就是三个运算符的天然性格记起来并不难。我第一次大量使用这套操作是在写一个资源管理模块时用32位整数记录32个资源占用状态。第k个资源空闲就是第k位为0分配就是把第k位置1。32个开关只占一个整数的内存而且判断“哪些资源可用”可以直接对整个整数做与运算一批一批地检查比循环数组高效得多。这就是“一个int当32个bool用”的雏形。3. 进阶玩法位掩码、集合枚举与状态压缩3.1 位掩码一个整数就是一排开关位掩码的思维模型很简单一个整数是一个比特数组每一位代表一个布尔状态。比如权限管理的经典案例读、写、执行三个权限分别映射到二进制的第2位、第1位、第0位#define PERM_READ (1 2) // 4 #define PERM_WRITE (1 1) // 2 #define PERM_EXEC (1 0) // 1 int permissions 0; permissions | PERM_READ | PERM_EXEC; // 授予读和执行 permissions ~PERM_WRITE; // 收回写权限 if (permissions PERM_READ) { // 有读权限 }这种设计的好处不止是省内存。它允许你一次操作多个权限标志permissions (PERM_READ | PERM_WRITE)可以同时判断两个权限也允许你把一组标志打包传参、存数据库。Linux系统的文件权限位就是最古老的实战案例rwx三组位组合起来才9个bit。我自己的体会是位掩码让代码里那些“本应该是一组布尔变量”的东西获得了整体操作的表达能力。它实际上就是“集合”的极简实现一个int能表示一个最多32个元素的集合元素在不在集合里查一下位就好。3.2 状态压缩动态规划里的“集合”变身整数状态压缩是位运算在算法里最重头的应用。核心思想是当一个DP状态需要记录“集合S里有哪些元素”直接用int mask表示这个集合第i位是1代表i在集合里。最经典的例子是旅行商问题的子集DP。定义dp[mask][i]表示“已经访问过mask集合中的城市当前停在城市i”的最短路径。初始化、转移、查状态的全过程就是反复对mask做位操作const int INF 0x3f3f3f3f; int dp[1 n][n]; memset(dp, INF, sizeof(dp)); dp[1 start][start] 0; for (int mask 0; mask (1 n); mask) { for (int i 0; i n; i) { if (!(mask (1 i))) continue; // i不在集合里跳过 for (int j 0; j n; j) { if (mask (1 j)) continue; // j已经访问过目标就是没访问过的点 int next_mask mask | (1 j); // 把j加入集合 dp[next_mask][j] min(dp[next_mask][j], dp[mask][i] cost[i][j]); } } }这里的mask (1 i)是“查询i是否在集合中”mask | (1 j)是“把新元素加入集合”。整个外循环遍历了从0到2^n - 1的所有集合这就是“状态压缩”的字面意思把一整个集合的状态压进一个整数里作为DP表格的一个维度。这种写法让很多原本需要哈希表或高维数组的DP获得了极简表达。代价是空间随元素数量指数增长所以状态压缩DP通常只能处理 n ≤ 20 这个量级。工程里也常见类似做法比如用一个long型当作64位布尔数组来追踪资源编号集合。3.3 枚举一个集合的全部子集一行代码里的数学如果要枚举一个集合的所有子集最简单的做法是对每个子集构造一个掩码sub循环0到mask。但如果只枚举mask的子集即只包含mask中已经出现的元素可以用下面这个经典写法for (int sub mask; sub; sub (sub - 1) mask) { // 处理子集sub } // 别忘了 sub 0 的子集需要额外处理这行代码的理解难度不低。关键在(sub - 1) mask每次把sub减一会产生一串低位上的变化然后再与mask做与运算把不属于mask的位全部掐掉。这个过程会遍历mask的全部非空子集当sub减到0时循环结束。举例mask 1011十进制的11它的非空子集有1011、1010、1001、1000、0011、0010、0001。这个循环会按二进制递减的顺序把它们都走一遍。枚举完非空子集后别漏了sub 0的空集。这个技巧的复杂度是O(3^n)如果对每个子集再枚举它的子集总次数是每个元素在“大集合、子集、不在集合”三种状态中分配总共有3的n次方种情况。很多枚举子集类题目时间复杂度就是这么定下来的。我第一次手推这个循环时花了半天但推通之后再看一堆“枚举子集”的题就跟看平路一样。3.4 计算二进制中1的个数Kernighan算法统计一个整数二进制表示里有多少个1这个指标叫popcount。最直接的办法是逐位检查循环32次但用前面讲的n (n - 1)可以只循环二进制中1的个数那么多次int countOnes(int n) { int count 0; while (n) { n n (n - 1); // 每次清除最低位的1 count; } return count; }比如n 13二进制是1101循环执行三次清除最低位11101 - 1100 - 1000 - 0000三次结束恰好有3个1。这个算法以Brian Kernighan的名字流传它在二进制的1比较稀疏的场景尤其高效。实际工程里C可以直接用内置的__builtin_popcountJava用Integer.bitCount它们在很多平台上都有硬件指令加速。popcount不只是炫技指标。拿奇偶校验来说数据传输过程中经常要统计一个字节里1的个数是不是偶数布隆过滤器里判断一组哈希位命中多少甚至连神经网络的二值化网络里都在用popcount做核心运算。基础操作一旦吃透上层能做的事情就铺开了。4. 算法题里的位运算经典套路4.1 最短路线的数组题全员异或找“只出现一次的数字”有一道经典面试题一个数组里除了某个元素只出现一次之外其他每个元素都恰好出现两次请找出那个孤家寡人。朴素解法是哈希表计数空间O(n)用异或可以做到时间O(n)、空间O(1)int findSingle(int arr[], int n) { int ans 0; for (int i 0; i n; i) { ans ^ arr[i]; } return ans; }原理就是前面说的两条性质x ^ x 0和x ^ 0 x。成对出现的元素在异或过程中互相抵消最后剩下的一定是那个只出现一次的元素。我第一次看到这个解法时觉得“这完全是魔术”后来理解了异或就是“模2相加”的本质就一点也不神奇了两个相同的二进制按位异或每一位都会消成0和“110”在模2意义下完全一致。这道题的变体也很多比如“两个只出现一次的数”先把全部数异或得到a ^ b再找到这个结果里任意一个为1的位按这个位把数组分成两组每组各自异或。核心思想还是“异或把成对的消掉靠不同的bit分组”。这套玩法理解了基本就算尝到位运算在算法题里的甜头。4.2 找出缺失的数下标与值一起异或另一个经典长度为n的数组包含0到n这n1个数中缺失的某一个。找出缺失值。不用数学求和用异或同样有简洁解法int missingNumber(int nums[], int n) { int ans 0; for (int i 0; i n; i) { ans ^ i ^ nums[i]; } ans ^ n; return ans; }这里的意思是我们把“应该有的下标0到n”全部异或一遍再把“数组里的实际值”也全部异或一遍。由于下标集合与数值集合基本都是同一个数字集合除了缺失的那个数在“应有值”里出现了一次、在“实际值”里没有对应项其他数字都是两两抵消。最后剩下的一定就是缺的那个数。这个思路的本质是给集合里的每个元素找“配对对象”。如果你写题目时遇到“找缺失”“找重复”“找唯一”的字符串处理都可以想一想能不能用异或来配对。它比求和做法更强的地方是如果数据里混着多组集合求和公式就不灵了异或依然能精准消去成对元素。4.3 快速幂与快速乘把指数拆成二进制不用循环n次而是用二进制的“倍增思想”计算a^n这就是快速幂long long fastPow(long long a, long long n, long long mod) { long long result 1; a % mod; while (n 0) { if (n 1) { result result * a % mod; } a a * a % mod; n 1; } return result; }原理一句话把指数n看成一串二进制位比如n 13(1101)那么a^13 a^(841) a^8 * a^4 * a^1。循环里不断让a自乘相当于从a^1走到a^2、a^4、a^8判断n 1就是在检查当前二进制位是否有值有值就乘进结果。每轮n 1把已经检查过的位移出去。快速乘也很常用形如a * b % mod当两个大数直接相乘会溢出时把乘法拆成二进制加法配合取模控制中间量大小。它和快速幂是同一套思想二进制展开 按位检查 倍增推进。这套组合在需要幂运算和大数运算的代码里几乎是标配。4.4 从lowbit到树状数组位运算点亮数据结构lowbit是位运算里最优雅的一个操作用来提取一个整数最低位的1所代表的值int lowbit(int x) { return x (-x); }它的正确性来自补码-x等于~x 1。举个例子x 12(1100)-x 01008位下写作11110100两者做与运算只有最低位的那个1被保留下来结果是4。无论x是几x (-x)得到的都是“只含最低位那一个1的整数”。树状数组就是建立在lowbit上的经典数据结构。它用lowbit来划分“管辖区间”维护前缀和的sum(i)和更新点值的add(i, delta)都用i lowbit(i)或i - lowbit(i)推进int bit[N]; void add(int i, int delta) { while (i N) { bit[i] delta; i lowbit(i); } } int sum(int i) { int res 0; while (i 0) { res bit[i]; i - lowbit(i); } return res; }这段代码的美妙之处在于更新和查询都只有O(log n)次操作而且整个索引推进过程完全靠位运算完成没有一个除法或取模。我第一次手写树状数组时就是把几个数字的lowbit值摆出来硬推推完之后彻底理解了这个数据结构的骨架。位运算在这里不是优化工具而是数据结构的理论基础。5. 避坑手册位运算代码的常见事故现场5.1 运算符优先级是最大的隐形杀手位运算符号的优先级普遍偏低尤其是、^、|它们比相等运算符还要低。拿2.1里那个判断奇偶的例子来说// 错误写法 if (n 1 0) { printf(偶数); }这段C代码会被解析成n (1 0)也就是n 0值为0整个条件永远为假。你本意是判断偶数结果无论n是什么if都不进入。这种bug在Java、C、C里都一样非常阴间。建议记下这条优先级链算术运算 移位 关系比较 相等判断 位与 异或 位或 逻辑与 逻辑或。实操经验是只要位运算出现在条件判断里无脑加括号。宁可多写两对括号也别让读代码的人对着运算符优先级表翻半天。场景易错写法安全写法判断奇偶if (n 1 0)if ((n 1) 0)判断是否为2的幂if (n (n-1) 0)if ((n (n - 1)) 0)检查第k位if (x (1 k) ! 0)if ((x (1 k)) ! 0)5.2 有符号右移和无符号右移很多bug的源头先说C/C里最典型的坑无符号整数的右移补0有符号整数的右移补符号位。所以-1 1在有符号语义下结果依然是-1因为符号位每次都被补回来而在无符号语义下0xFFFFFFFF 1会变成0x7FFFFFFF。同一个位模式两种解释差出几亿。Java更精细一些是算术右移补符号位是无符号右移补0。写代码时如果混淆处理图片像素、哈希值时会突然冒出一堆负数。Python则走了另一条路整数是无限位宽的负数右移结果等价于floor(n / 2)所以-3 1 -2和C的算术右移一致但在“取某几个bit”的场景Python的负数位运算语义跟C差别很大跨语言移植时千万别默认行为一致。我的建议是涉及负数右移时写一行注释标明预期行为。别指望所有人都跟你一样清楚当前语言的实现细节。5.3 位运算不是越多越好可读性也是性能指标最后必须提醒一句位运算是工具不是勋章。我在实际工作中见过为了炫技把所有布尔判断都改成位运算、结果同事完全看不懂的代码。可读性差的代码维护成本极高而位运算占的那几个微秒在绝大多数业务系统里根本不值一提。我的使用原则很简单热点路径比如哈希索引计算、像素级循环、数据包解析位运算大胆用并配注释。底层库与嵌入式内存受限、CPU周期敏感位运算是必要的生存技能。业务逻辑层能读优先if (permissions 0)比if ((permissions mask) 0)在业务上更直白的地方就别硬拗。算法题与竞赛状态压缩、枚举子集、快速幂这些场景位运算就是标准解法必须熟练掌握。我在某个项目中曾把一段频繁调用的模块数据解析从多个布尔字段改成一个int标志位性能提升与内存节省都非常可观同时我特地在结构体旁边写了注释说明每个bit的含义。后来同事接手时靠注释轻松看懂这种“用位运算但不滥用”的平衡感才是最成熟的写法。最后分享一个我自己的习惯学位运算时别只看别人总结好的式子一定要在草稿纸上手动展开几个二进制数把补码取反、加一、与运算都走一遍。比如亲手验证一下x (-x)如何提取最低位你会突然有种“原来CPU是这么想问题”的通透感。这套基本功我到现在还在用排查一些诡异数据异常时把变量按二进制拆开看往往比追代码逻辑更先找到真相。