说起“位运算”很多人脑袋里浮现的第一行代码可能是n 1 1或者一个^用在交换两数上。但在真实项目和算法比赛里位运算的价值远不止面试炫技——它是少数几种“从底层逻辑上解决问题”的工具状态压缩、权限校验、布隆过滤器、嵌入式寄存器操作哪一样都离不开它。这篇文章就围绕“常见位运算”这一主题把基本的运算符、高频套路、真实场景和防坑经验一次性梳理清楚适合正在刷算法题的学生、写业务代码想优化性能的工程师以及需要跟底层硬件打交道的开发者。我会尽量用大白话拆解原理同时给出一看就能用的代码和踩坑记录。1. 位运算的基本盘四个运算符加两种移位1.1 一张真值表讲清按位与、或、异或、取反位运算操作的是二进制位也就是每个比特位上的 0 或 1。按位与、按位或|、按位异或^、按位取反~是最基础的四个操作其实它们各自的规则用一句话就能说明白与两个位都是 1 才是 1否则是 0。类似于“两个条件同时满足才成立”。或|两个位只要有一个是 1 就是 1否则是 0。类似于“至少一个满足就成立”。异或^两个位不相同为 1相同为 0。它的核心含义是“找不同”。取反~0 变 11 变 0即按位翻转。大部分入门材料会用一张真值表把A B、A | B、A ^ B的存在关系列出来但我觉得真正实用的做法是把它们“翻译”成逻辑判断方便在写代码时快速反应假设A 5二进制为101B 3二进制为011。那么A B 001即十进制的 1。A | B 111即十进制的 7。A ^ B 110即十进制的 6。~A ...11111010这里的高位会补 1具体结果看语言对有符号整数的表示方式。很多新手第一次看到取反会懵因为在多数语言里~5的结果并不是“101 取反后的 010”即 2而是-6。原因是有符号数用补码表示~5等价于-5 - 1。这个特性很重要后面讲lowbit和取绝对值时会用到。1.2 左移和右移别小看这两个移位移位运算符也是位运算家族的嫡系成员。左移将二进制位整体向左移动右侧补 0每左移一位相当于乘以 2。右移分为逻辑右移和算术右移这一点特别容易栽跟头。逻辑右移高位补 0用于无符号数。算术右移高位补符号位也就是正数补 0、负数补 1。大多数语言里的有符号数默认是算术右移。举个例子-4的二进制补码是...11111100在 Python 或 C 中执行-4 1得到-2因为是算术右移高位继续补 1整体向右挪一位后依然保持负数语义正好等价于除以 2。如果你希望做逻辑右移就需要使用专门的运算符比如 JavaScript 里的或者先转成无符号类型再移。左移 1 位相当于乘 2右移 1 位相当于整除 2 并向下取整。这一点比乘除法快但前提是真的需要这种整数语义。比如要判断某个数是不是 2 的整数次幂或者要从整数中提取某个连续区间段移位都是最直白的写法。1.3 为什么位运算能快人一等位运算之所以被算法竞赛选手和底层工程师偏爱核心原因在于它绕开了“高级抽象”。CPU 处理加法、乘法时需要把数据送到运算器经过多级电路才有结果而位移和逻辑运算在很多处理器上只需要一个时钟周期甚至更短。你写a * 2时现代编译器通常会优化成a 1说明编译器也明白这个道理。不过在业务层写代码位运算带来的性能提升往往微乎其微真正的价值更多体现在“数据结构和逻辑表达”本身。最典型的就是状态压缩一个int里有 32 个比特位可以用它表示 32 个开关如果改用 32 个布尔值光是对象头和内存对齐就要多花好几倍空间。这种空间上的碾压在高并发任务或单片机上表现得尤其明显。2. 高频套路拿来就能用的位运算技巧2.1 判断奇偶n 1 背后的原理二进制的最低位LSB决定了整数的奇偶性最低位是 1 就是奇数是 0 就是偶数。所以n 1可以替代n % 2if (n 1) { // n 是奇数 } else { // n 是偶数 }这里要注意的优先级比低所以写n 1 1实际上会被解析成n 1 1结果就错了。正确写法是if (n 1)或显式加括号if ((n 1) 1)。我见过不少人在循环里用n % 2判断奇偶这当然没错但在追求极致性能的地底层代码里n 1确实会有可观测的差距。更重要的是这一个细节能让你在大规模状态遍历时省掉不必要的模运算开销。2.2 干掉最低位 1n (n - 1) 和 lowbitn (n - 1)是位运算里最经典的一行代码作用是“将 n 的二进制表示中最右边的 1 变成 0”。这个操作能做的事太多了判断 2 的幂如果n 0且n (n - 1) 0那么 n 就是 2 的幂。统计 1 的个数不断执行n (n - 1)每执行一次消掉一个 1计数加 1直到 n 变成 0。组合枚举遍历状态子集。与它配套的还有一个lowbit技巧也就是取到二进制中最右边的 1lowbit(x) x (-x)原理是利用补码运算-x等价于x取反再加 1取反加 1 之后原来第一个 1 前面的位全部变成 0只有这个 1 及其低位保持不变。x (-x)得到的结果就是只包含最低位那个 1 的数。比如lowbit(10)10 的二进制是1010-10的补码是0110的取反再加 1此处按 4 位二进制示意与运算后得到0010也就是 2。这个技巧在树状数组Fenwick Tree里几乎是核心操作。2.3 异或的幂找不同、去重、交换异或运算有三个性质值得刻在脑子里x ^ x 0自己和自己做异或结果是 0。x ^ 0 x和 0 做异或结果不变。交换律和结合律无论怎么调整顺序结果都不变。基于这些性质最常见的应用场景有两个。第一个场景是“找出唯一出现一次的元素”。如果数组中其他元素都出现两次只有一个出现一次那么全体元素做异或出现两次的全部抵消成 0最后剩下的就是那个唯一元素。int findSingle(vectorint nums) { int ans 0; for (int v : nums) ans ^ v; return ans; }我当年第一次看到这个解法时觉得特别巧妙因为它不需要哈希表不需要排序空间复杂度是 O(1)时间也只需要一趟遍历。这个思路还可以扩展到“一个数组里其他元素都出现三次找唯一出现一次的数”不过那种场景需要统计每个二进制位上的 1 的个数然后对 3 取余稍复杂一点但依然是用位的思路。第二个场景是不用临时变量交换两个整数a ^ b; b ^ a; a ^ b;这个写法虽然不太建议在生产代码里用可读性太差但它很能说明异或的性质第一步之后a 变成 a ^ b第二步b 等于 b ^ (a ^ b) a第三步a 变成 (a ^ b) ^ a b。整个过程没有额外的中间变量在寄存器极度紧张的嵌入式场景中早期确实有人会这么写。2.4 掩码操作置1、清0、翻转、查询一把梭掩码mask本质上是“选中某些位”的模板。比如要操作第 k 位从 0 开始计数可以这样构造掩码置为 1x | (1 k)清零x ~(1 k)翻转x ^ (1 k)查询(x k) 1这套操作可以被组合成非常优雅的“位图”bitmap。假设你有一组 id范围在 0 到 31 之间你想记录哪些 id 已经出现过那么一个 32 位的整数就够了。int bitmap 0; // 插入 id3 bitmap | (1 3); // 判断 id3 是否存在 if ((bitmap 3) 1) { /* exist */ } // 删除 id3 bitmap ~(1 3);这种写法在处理大数据去重、待办状态集合时非常高效。我在一个模拟项目里需要同时记录多个用户的任务完成状态如果用结构体加布尔字段一套逻辑要写一长串条件判断改用掩码之后只需要一个整数就能完成状态流的迁移和判断代码量直接少了一半。3. 真实场景从权限系统到状态压缩3.1 用位标志位重构权限判断大多数业务系统在做权限验证时会写类似if (user.isAdmin user.canEdit user.canDelete)的代码字段一多就乱。位标志位是更好的组织方式给每个权限分配一个独立的二进制位权限集合整体存成一个整数。// 定义权限位 const int PERM_VIEW 1 0; // 1 const int PERM_EDIT 1 1; // 2 const int PERM_DELETE 1 2; // 4 const int PERM_ADMIN 1 3; // 8 // 给某个角色赋权 int rolePerm PERM_VIEW | PERM_EDIT; // 判断是否有权限 if ((rolePerm PERM_EDIT) ! 0) { ... } // 追加权限 rolePerm | PERM_DELETE; // 回收权限 rolePerm ~PERM_DELETE;这套方案的好处是什么权限判断从多次比较变成一次按位与运算数据库存储时也只需要一个整数列。更重要的是权限的组合天然支持“多选”不存在枚举组合爆炸问题。你在一个系统里可能同时需要“查看 编辑 删除”和“查看 删除”如果枚举纯组合数量会指数上涨而位标志只需要在代码里动态去或运算。3.2 状态压缩把一整个集合装进一个 int状态压缩动态规划位运算 DP是算法竞赛里的重头戏它的核心思想就是用二进制位表示集合成员。比如旅行商问题有 n 个城市要遍历状态的集合用S表示已经访问过的城市集合dp[S][i]表示访问集合 S 并且最后停留在城市 i 的最短路径。如果不压缩你需要一个布尔数组去记录访问历史维度根本无法表达压缩之后一个整数就完整代表一个集合。写状态压缩 DP 时经常会用到三个操作判断城市 j 是否在集合 S 中if (S (1 j))把城市 j 加入集合S | (1 j)从集合 S 中移除城市 jS ^ (1 j)或S ~(1 j)我在做模拟项目 X 时需要枚举多个设备的状态组合每个设备有开关两种状态。设备数量是 12如果用嵌套循环处理 2 的 12 次方种组合代码会包含 12 层循环而用一个int mask从 0 遍历到(1 12) - 1然后通过位操作拆解每一位逻辑清晰得多扩展性也直接拉满。3.3 嵌入式与网络协议里的位字段在很多网络协议里包头设计者会刻意把多个标志位塞进一个字节。比如某个协议包头里包含版本号、消息类型、是否加密、是否重传如果用四个独立变量接收传输效率低下不说解析时还要处理字节对齐。正确做法是定义一个结构体位字段或者直接对原始字节做位运算uint8_t header receivedByte; uint8_t version (header 6) 0x03; // 高 2 位 uint8_t msgType (header 4) 0x03; // 中间 2 位 uint8_t encrypted (header 3) 0x01; // 第 3 位 uint8_t retry header 0x07; // 低 3 位嵌入式里操作寄存器就更直接了。单片机的 GPIO 方向寄存器可能要求在某个地址的第 5 位置 1 才能把对应引脚设为输出你不可能像写业务代码那样“新建一个对象再赋值”只能直接对寄存器数值做位运算GPIO_DIR | (1 5); // 设置为输出 GPIO_DATA ^ (1 5); // 翻转引脚电平所以如果你以后要做嵌入式、驱动开发或者协议解析位运算是躲不开的基本功。3.4 哈希表中的位操作与性能优化不要以为位运算只出现在底层层面上哈希表里也经常能看到它的影子。很多哈希表在计算数组下标时会先用哈希函数算出一个大整数然后对容量取模。如果容量是 2 的幂取模运算可以改写成按位与运算index hash (capacity - 1)这个转换在容量为 2 的幂时完全等价于取模但硬件执行速度更快。这就是为什么有些语言运行时的哈希表默认容量是 2 的 n 次幂。布隆过滤器就更典型了它本身就是用若干个哈希函数映射到一个位数组上每个哈希函数负责把某位置 1查询时检查所有映射位是否都是 1。这个结构从数据表示的层面就是位运算的直接应用。4. 竞赛和面试经典这些题一看就是位运算4.1 判断一个数是不是 2 的幂先看最基本版本bool isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }为什么n (n - 1) 0就说明是 2 的幂因为 2 的幂在二进制里只有一个 1比如 8 是1000。8 - 1 7是0111两者按位与得到 0。而像 10 这样的数二进制是101010 - 1 9是1001与之后是1000不为 0。这个判断复杂度是 O(1)不需要循环。很多新手第一反应用while (n % 2 0) n / 2来判断正确是正确但不够优雅而且涉及多次除法和分支不如一行位运算干净。4.2 统计二进制中 1 的个数一个朴素的解决方案是循环检查每一位int count 0; while (n) { count n 1; n 1; }这个写法需要循环“二进制位数”那么多次。如果 n 很大但 1 的个数很少用n (n - 1)会高效得多int countOnes(int n) { int count 0; while (n) { n (n - 1); count; } return count; }循环次数等于 1 的个数。这个技巧在图像处理里计算位图黑点数量、或者在网络设备统计路由前缀匹配情况时都有实际应用。如果 n 的范围固定工程上还会用打表法也就是查表用空间换时间但理解位运算本质才是基础。4.3 找出唯一出现一次的数字前面已经讲过用异或实现这里再补充一个进阶版本给定一个整数数组有两个数字只出现一次其他都出现两次找出这两个数。思路也是位运算先把全体数字异或一遍得到a ^ b因为a不等于b所以这个值至少有一位是 1。找到那一位用lowbit然后根据这一位是 0 还是 1 把数组分成两组每组单独异或就能分别得到 a 和 b。vectorint findTwoSingle(vectorint nums) { int xorAll 0; for (int v : nums) xorAll ^ v; int lowbit xorAll (-xorAll); int a 0, b 0; for (int v : nums) { if (v lowbit) a ^ v; else b ^ v; } return {a, b}; }这类题目在面试中出现频率不低因为它的解法空间和时间都很漂亮而且能真实反映出一个人对二进制有没有直觉。4.4 不用临时变量交换两个数虽然前面已经提过但单独拎出来说一个重点这个技巧在 C/C 里能跑但是在某些情况下会有问题比如当a和b指向同一个内存地址时三次异或后结果会变成 0。所以如果真要在数组里交换两个元素arr[i]和arr[j]且i可能等于j千万不要这么写。if (i j) return; // 必须先做保护 arr[i] ^ arr[j]; arr[j] ^ arr[i]; arr[i] ^ arr[j];这其实是一个非常好的“理论 vs 实践”案例。平时写业务代码完全没必要为了秀技巧牺牲可读性直接用标准库的swap即可。但理解原理能帮你快速看懂一些底层库里的经典实现。4.5 快速取绝对值与符号判断取绝对值的位运算实现如下int abs(int x) { int sign x 31; // 全 0 或全 1取决于正负 return (x ^ sign) - sign; }这个技巧的原理是如果 x 是非负数sign 0x ^ 0 - 0 x如果 x 是负数sign -1全 1x ^ (-1)相当于取反再减(-1)等于取反加 1正好是补码转换得到正数。不过这个写法依赖算术右移和补码表示可移植性不像数学库那么好生产环境直接用abs就行当作理解补码的练习很合适。类似的还有“判断两个整数符号是否相同”(a ^ b) 0为真则同号。原理是符号位不同时异或结果的符号位为 1负数表示结果为负。5. 防坑指南位运算的常见问题和排查心得5.1 优先级坑为什么 a b c 结果不对位运算符的优先级很容易被忽略尤其是、^、|都低于。你写a b c语言会先算b c把布尔结果再和a做按位与最终得到完全不同的结果。这是初学者最常见的问题解决办法只有一个涉及位运算的比较场景一律加括号。if ((a b) c) { ... } if ((a mask) ! 0) { ... }我在代码评审的时候看到过很多次类似的 bug尤其是来自其他语言转过来的同事。只要看到位运算后面跟着比较运算符几乎可以断定有潜在问题。5.2 右移的符号问题算术位移与逻辑位移前面讲了算术右移会补符号位这在需要只移动数值位时会造成干扰。比如把一个有符号整数直接右移来取它的某一部分负数移位后高位全部补成 1结果会变成一个非常大的负值。解决办法是先把整数转成无符号类型或者使用明确是逻辑右移的操作。uint32_t x static_castuint32_t(n); uint8_t byte1 (x 8) 0xff;另外对有符号负数做右移 除以 2 也不完全等价。-3 1在 C 里结果是-2因为它是向下取整而-3 / 2的结果通常是-1向零取整。如果你真的需要“除以 2 向下取整”的语义算术右移倒是可以帮你做到但这要和业务预期对齐不然就是隐藏 bug。5.3 语言差异Python 的无限整数与 JavaScript 的 32 位陷阱不同语言对位运算的实现细节差异很大。Python 的整数是无限精度的位运算结果不会溢出但这也意味着负数取反会得到一个看起来“特别长”的数。比如 Python 里~5是-6这没问题但如果想模拟 C 语言的 32 位无符号效果你需要手动用掩码截断def unsigned(n): return n 0xffffffffJavaScript 更特殊它的位运算先把操作数转成 32 位有符号整数计算结果再转回普通数字。也就是说2147483647 1在 JavaScript 里会得出一个负数因为移位后超出了 32 位有符号范围。如果你用 JS 做二进制协议解析不理解这一点会踩到很多坑。另外Go 语言区分有符号和无符号整数的移位Rust 在 debug 模式下移位溢出直接 panic这些言行差异都说明了同一个问题位运算不是“语言无关的语法糖”而是和底层表示强绑定的操作。跨语言迁移时不能只看运算符还要看类型系统。5.4 性能错觉什么时候不该用位运算写代码时经常有人为了“优化”而强行把逻辑改成位运算比如把x % 2改成x 1这没问题但如果你的项目是业务系统数据库查询才是瓶颈位运算省下的那几个纳秒完全可以忽略。而且位运算代码可读性差团队后续维护成本高容易埋下隐藏 bug。合理的取舍是如果操作的是状态集合、权限标志、协议解析、大量循环内的固定模式位运算值得用如果只是偶尔判断奇偶直接用x % 2即可。现代编译器的优化能力很强很多简单的位操作它本身就会自动完成你不需要靠手写位运算来表达意图。注意有位开发者在把业务逻辑“位运算化”时忘了考虑可扩展性。后来系统新增了一个权限维度原来的位标志整个设计就被迫重写。位运算好用但它适合的是“位模式稳定、不频繁扩张”的场景这一点在设计之初就要想清楚。最后分享一个我自己的感悟。很多人学位运算一开始会觉得“会做题就行”但真正让它产生价值的节点是你开始理解二进制是计算机的母语。无论是编译器优化、网络协议解析、数据压缩还是高并发状态管理底层都逃不开位的组合与变换。做算法题时多看几个位运算的经典解法写业务代码时有意识地用掩码组织状态慢慢你会在“人的逻辑”和“机器的逻辑”之间建立一种直觉这种直觉在排查疑难 bug 时尤其好用。如果你正在刷题建议把第 4 节里的几道题手写一遍再对照源码看每一步的位变化胜过刷十道套模板的题。 
长河君 · 2026/10/22 15:41:03 · 阅读 1.2k 位运算实战指南：从二进制基础到状态压缩与权限系统
说起“位运算”很多人脑袋里浮现的第一行代码可能是n 1 1或者一个^用在交换两数上。但在真实项目和算法比赛里位运算的价值远不止面试炫技——它是少数几种“从底层逻辑上解决问题”的工具状态压缩、权限校验、布隆过滤器、嵌入式寄存器操作哪一样都离不开它。这篇文章就围绕“常见位运算”这一主题把基本的运算符、高频套路、真实场景和防坑经验一次性梳理清楚适合正在刷算法题的学生、写业务代码想优化性能的工程师以及需要跟底层硬件打交道的开发者。我会尽量用大白话拆解原理同时给出一看就能用的代码和踩坑记录。1. 位运算的基本盘四个运算符加两种移位1.1 一张真值表讲清按位与、或、异或、取反位运算操作的是二进制位也就是每个比特位上的 0 或 1。按位与、按位或|、按位异或^、按位取反~是最基础的四个操作其实它们各自的规则用一句话就能说明白与两个位都是 1 才是 1否则是 0。类似于“两个条件同时满足才成立”。或|两个位只要有一个是 1 就是 1否则是 0。类似于“至少一个满足就成立”。异或^两个位不相同为 1相同为 0。它的核心含义是“找不同”。取反~0 变 11 变 0即按位翻转。大部分入门材料会用一张真值表把A B、A | B、A ^ B的存在关系列出来但我觉得真正实用的做法是把它们“翻译”成逻辑判断方便在写代码时快速反应假设A 5二进制为101B 3二进制为011。那么A B 001即十进制的 1。A | B 111即十进制的 7。A ^ B 110即十进制的 6。~A ...11111010这里的高位会补 1具体结果看语言对有符号整数的表示方式。很多新手第一次看到取反会懵因为在多数语言里~5的结果并不是“101 取反后的 010”即 2而是-6。原因是有符号数用补码表示~5等价于-5 - 1。这个特性很重要后面讲lowbit和取绝对值时会用到。1.2 左移和右移别小看这两个移位移位运算符也是位运算家族的嫡系成员。左移将二进制位整体向左移动右侧补 0每左移一位相当于乘以 2。右移分为逻辑右移和算术右移这一点特别容易栽跟头。逻辑右移高位补 0用于无符号数。算术右移高位补符号位也就是正数补 0、负数补 1。大多数语言里的有符号数默认是算术右移。举个例子-4的二进制补码是...11111100在 Python 或 C 中执行-4 1得到-2因为是算术右移高位继续补 1整体向右挪一位后依然保持负数语义正好等价于除以 2。如果你希望做逻辑右移就需要使用专门的运算符比如 JavaScript 里的或者先转成无符号类型再移。左移 1 位相当于乘 2右移 1 位相当于整除 2 并向下取整。这一点比乘除法快但前提是真的需要这种整数语义。比如要判断某个数是不是 2 的整数次幂或者要从整数中提取某个连续区间段移位都是最直白的写法。1.3 为什么位运算能快人一等位运算之所以被算法竞赛选手和底层工程师偏爱核心原因在于它绕开了“高级抽象”。CPU 处理加法、乘法时需要把数据送到运算器经过多级电路才有结果而位移和逻辑运算在很多处理器上只需要一个时钟周期甚至更短。你写a * 2时现代编译器通常会优化成a 1说明编译器也明白这个道理。不过在业务层写代码位运算带来的性能提升往往微乎其微真正的价值更多体现在“数据结构和逻辑表达”本身。最典型的就是状态压缩一个int里有 32 个比特位可以用它表示 32 个开关如果改用 32 个布尔值光是对象头和内存对齐就要多花好几倍空间。这种空间上的碾压在高并发任务或单片机上表现得尤其明显。2. 高频套路拿来就能用的位运算技巧2.1 判断奇偶n 1 背后的原理二进制的最低位LSB决定了整数的奇偶性最低位是 1 就是奇数是 0 就是偶数。所以n 1可以替代n % 2if (n 1) { // n 是奇数 } else { // n 是偶数 }这里要注意的优先级比低所以写n 1 1实际上会被解析成n 1 1结果就错了。正确写法是if (n 1)或显式加括号if ((n 1) 1)。我见过不少人在循环里用n % 2判断奇偶这当然没错但在追求极致性能的地底层代码里n 1确实会有可观测的差距。更重要的是这一个细节能让你在大规模状态遍历时省掉不必要的模运算开销。2.2 干掉最低位 1n (n - 1) 和 lowbitn (n - 1)是位运算里最经典的一行代码作用是“将 n 的二进制表示中最右边的 1 变成 0”。这个操作能做的事太多了判断 2 的幂如果n 0且n (n - 1) 0那么 n 就是 2 的幂。统计 1 的个数不断执行n (n - 1)每执行一次消掉一个 1计数加 1直到 n 变成 0。组合枚举遍历状态子集。与它配套的还有一个lowbit技巧也就是取到二进制中最右边的 1lowbit(x) x (-x)原理是利用补码运算-x等价于x取反再加 1取反加 1 之后原来第一个 1 前面的位全部变成 0只有这个 1 及其低位保持不变。x (-x)得到的结果就是只包含最低位那个 1 的数。比如lowbit(10)10 的二进制是1010-10的补码是0110的取反再加 1此处按 4 位二进制示意与运算后得到0010也就是 2。这个技巧在树状数组Fenwick Tree里几乎是核心操作。2.3 异或的幂找不同、去重、交换异或运算有三个性质值得刻在脑子里x ^ x 0自己和自己做异或结果是 0。x ^ 0 x和 0 做异或结果不变。交换律和结合律无论怎么调整顺序结果都不变。基于这些性质最常见的应用场景有两个。第一个场景是“找出唯一出现一次的元素”。如果数组中其他元素都出现两次只有一个出现一次那么全体元素做异或出现两次的全部抵消成 0最后剩下的就是那个唯一元素。int findSingle(vectorint nums) { int ans 0; for (int v : nums) ans ^ v; return ans; }我当年第一次看到这个解法时觉得特别巧妙因为它不需要哈希表不需要排序空间复杂度是 O(1)时间也只需要一趟遍历。这个思路还可以扩展到“一个数组里其他元素都出现三次找唯一出现一次的数”不过那种场景需要统计每个二进制位上的 1 的个数然后对 3 取余稍复杂一点但依然是用位的思路。第二个场景是不用临时变量交换两个整数a ^ b; b ^ a; a ^ b;这个写法虽然不太建议在生产代码里用可读性太差但它很能说明异或的性质第一步之后a 变成 a ^ b第二步b 等于 b ^ (a ^ b) a第三步a 变成 (a ^ b) ^ a b。整个过程没有额外的中间变量在寄存器极度紧张的嵌入式场景中早期确实有人会这么写。2.4 掩码操作置1、清0、翻转、查询一把梭掩码mask本质上是“选中某些位”的模板。比如要操作第 k 位从 0 开始计数可以这样构造掩码置为 1x | (1 k)清零x ~(1 k)翻转x ^ (1 k)查询(x k) 1这套操作可以被组合成非常优雅的“位图”bitmap。假设你有一组 id范围在 0 到 31 之间你想记录哪些 id 已经出现过那么一个 32 位的整数就够了。int bitmap 0; // 插入 id3 bitmap | (1 3); // 判断 id3 是否存在 if ((bitmap 3) 1) { /* exist */ } // 删除 id3 bitmap ~(1 3);这种写法在处理大数据去重、待办状态集合时非常高效。我在一个模拟项目里需要同时记录多个用户的任务完成状态如果用结构体加布尔字段一套逻辑要写一长串条件判断改用掩码之后只需要一个整数就能完成状态流的迁移和判断代码量直接少了一半。3. 真实场景从权限系统到状态压缩3.1 用位标志位重构权限判断大多数业务系统在做权限验证时会写类似if (user.isAdmin user.canEdit user.canDelete)的代码字段一多就乱。位标志位是更好的组织方式给每个权限分配一个独立的二进制位权限集合整体存成一个整数。// 定义权限位 const int PERM_VIEW 1 0; // 1 const int PERM_EDIT 1 1; // 2 const int PERM_DELETE 1 2; // 4 const int PERM_ADMIN 1 3; // 8 // 给某个角色赋权 int rolePerm PERM_VIEW | PERM_EDIT; // 判断是否有权限 if ((rolePerm PERM_EDIT) ! 0) { ... } // 追加权限 rolePerm | PERM_DELETE; // 回收权限 rolePerm ~PERM_DELETE;这套方案的好处是什么权限判断从多次比较变成一次按位与运算数据库存储时也只需要一个整数列。更重要的是权限的组合天然支持“多选”不存在枚举组合爆炸问题。你在一个系统里可能同时需要“查看 编辑 删除”和“查看 删除”如果枚举纯组合数量会指数上涨而位标志只需要在代码里动态去或运算。3.2 状态压缩把一整个集合装进一个 int状态压缩动态规划位运算 DP是算法竞赛里的重头戏它的核心思想就是用二进制位表示集合成员。比如旅行商问题有 n 个城市要遍历状态的集合用S表示已经访问过的城市集合dp[S][i]表示访问集合 S 并且最后停留在城市 i 的最短路径。如果不压缩你需要一个布尔数组去记录访问历史维度根本无法表达压缩之后一个整数就完整代表一个集合。写状态压缩 DP 时经常会用到三个操作判断城市 j 是否在集合 S 中if (S (1 j))把城市 j 加入集合S | (1 j)从集合 S 中移除城市 jS ^ (1 j)或S ~(1 j)我在做模拟项目 X 时需要枚举多个设备的状态组合每个设备有开关两种状态。设备数量是 12如果用嵌套循环处理 2 的 12 次方种组合代码会包含 12 层循环而用一个int mask从 0 遍历到(1 12) - 1然后通过位操作拆解每一位逻辑清晰得多扩展性也直接拉满。3.3 嵌入式与网络协议里的位字段在很多网络协议里包头设计者会刻意把多个标志位塞进一个字节。比如某个协议包头里包含版本号、消息类型、是否加密、是否重传如果用四个独立变量接收传输效率低下不说解析时还要处理字节对齐。正确做法是定义一个结构体位字段或者直接对原始字节做位运算uint8_t header receivedByte; uint8_t version (header 6) 0x03; // 高 2 位 uint8_t msgType (header 4) 0x03; // 中间 2 位 uint8_t encrypted (header 3) 0x01; // 第 3 位 uint8_t retry header 0x07; // 低 3 位嵌入式里操作寄存器就更直接了。单片机的 GPIO 方向寄存器可能要求在某个地址的第 5 位置 1 才能把对应引脚设为输出你不可能像写业务代码那样“新建一个对象再赋值”只能直接对寄存器数值做位运算GPIO_DIR | (1 5); // 设置为输出 GPIO_DATA ^ (1 5); // 翻转引脚电平所以如果你以后要做嵌入式、驱动开发或者协议解析位运算是躲不开的基本功。3.4 哈希表中的位操作与性能优化不要以为位运算只出现在底层层面上哈希表里也经常能看到它的影子。很多哈希表在计算数组下标时会先用哈希函数算出一个大整数然后对容量取模。如果容量是 2 的幂取模运算可以改写成按位与运算index hash (capacity - 1)这个转换在容量为 2 的幂时完全等价于取模但硬件执行速度更快。这就是为什么有些语言运行时的哈希表默认容量是 2 的 n 次幂。布隆过滤器就更典型了它本身就是用若干个哈希函数映射到一个位数组上每个哈希函数负责把某位置 1查询时检查所有映射位是否都是 1。这个结构从数据表示的层面就是位运算的直接应用。4. 竞赛和面试经典这些题一看就是位运算4.1 判断一个数是不是 2 的幂先看最基本版本bool isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }为什么n (n - 1) 0就说明是 2 的幂因为 2 的幂在二进制里只有一个 1比如 8 是1000。8 - 1 7是0111两者按位与得到 0。而像 10 这样的数二进制是101010 - 1 9是1001与之后是1000不为 0。这个判断复杂度是 O(1)不需要循环。很多新手第一反应用while (n % 2 0) n / 2来判断正确是正确但不够优雅而且涉及多次除法和分支不如一行位运算干净。4.2 统计二进制中 1 的个数一个朴素的解决方案是循环检查每一位int count 0; while (n) { count n 1; n 1; }这个写法需要循环“二进制位数”那么多次。如果 n 很大但 1 的个数很少用n (n - 1)会高效得多int countOnes(int n) { int count 0; while (n) { n (n - 1); count; } return count; }循环次数等于 1 的个数。这个技巧在图像处理里计算位图黑点数量、或者在网络设备统计路由前缀匹配情况时都有实际应用。如果 n 的范围固定工程上还会用打表法也就是查表用空间换时间但理解位运算本质才是基础。4.3 找出唯一出现一次的数字前面已经讲过用异或实现这里再补充一个进阶版本给定一个整数数组有两个数字只出现一次其他都出现两次找出这两个数。思路也是位运算先把全体数字异或一遍得到a ^ b因为a不等于b所以这个值至少有一位是 1。找到那一位用lowbit然后根据这一位是 0 还是 1 把数组分成两组每组单独异或就能分别得到 a 和 b。vectorint findTwoSingle(vectorint nums) { int xorAll 0; for (int v : nums) xorAll ^ v; int lowbit xorAll (-xorAll); int a 0, b 0; for (int v : nums) { if (v lowbit) a ^ v; else b ^ v; } return {a, b}; }这类题目在面试中出现频率不低因为它的解法空间和时间都很漂亮而且能真实反映出一个人对二进制有没有直觉。4.4 不用临时变量交换两个数虽然前面已经提过但单独拎出来说一个重点这个技巧在 C/C 里能跑但是在某些情况下会有问题比如当a和b指向同一个内存地址时三次异或后结果会变成 0。所以如果真要在数组里交换两个元素arr[i]和arr[j]且i可能等于j千万不要这么写。if (i j) return; // 必须先做保护 arr[i] ^ arr[j]; arr[j] ^ arr[i]; arr[i] ^ arr[j];这其实是一个非常好的“理论 vs 实践”案例。平时写业务代码完全没必要为了秀技巧牺牲可读性直接用标准库的swap即可。但理解原理能帮你快速看懂一些底层库里的经典实现。4.5 快速取绝对值与符号判断取绝对值的位运算实现如下int abs(int x) { int sign x 31; // 全 0 或全 1取决于正负 return (x ^ sign) - sign; }这个技巧的原理是如果 x 是非负数sign 0x ^ 0 - 0 x如果 x 是负数sign -1全 1x ^ (-1)相当于取反再减(-1)等于取反加 1正好是补码转换得到正数。不过这个写法依赖算术右移和补码表示可移植性不像数学库那么好生产环境直接用abs就行当作理解补码的练习很合适。类似的还有“判断两个整数符号是否相同”(a ^ b) 0为真则同号。原理是符号位不同时异或结果的符号位为 1负数表示结果为负。5. 防坑指南位运算的常见问题和排查心得5.1 优先级坑为什么 a b c 结果不对位运算符的优先级很容易被忽略尤其是、^、|都低于。你写a b c语言会先算b c把布尔结果再和a做按位与最终得到完全不同的结果。这是初学者最常见的问题解决办法只有一个涉及位运算的比较场景一律加括号。if ((a b) c) { ... } if ((a mask) ! 0) { ... }我在代码评审的时候看到过很多次类似的 bug尤其是来自其他语言转过来的同事。只要看到位运算后面跟着比较运算符几乎可以断定有潜在问题。5.2 右移的符号问题算术位移与逻辑位移前面讲了算术右移会补符号位这在需要只移动数值位时会造成干扰。比如把一个有符号整数直接右移来取它的某一部分负数移位后高位全部补成 1结果会变成一个非常大的负值。解决办法是先把整数转成无符号类型或者使用明确是逻辑右移的操作。uint32_t x static_castuint32_t(n); uint8_t byte1 (x 8) 0xff;另外对有符号负数做右移 除以 2 也不完全等价。-3 1在 C 里结果是-2因为它是向下取整而-3 / 2的结果通常是-1向零取整。如果你真的需要“除以 2 向下取整”的语义算术右移倒是可以帮你做到但这要和业务预期对齐不然就是隐藏 bug。5.3 语言差异Python 的无限整数与 JavaScript 的 32 位陷阱不同语言对位运算的实现细节差异很大。Python 的整数是无限精度的位运算结果不会溢出但这也意味着负数取反会得到一个看起来“特别长”的数。比如 Python 里~5是-6这没问题但如果想模拟 C 语言的 32 位无符号效果你需要手动用掩码截断def unsigned(n): return n 0xffffffffJavaScript 更特殊它的位运算先把操作数转成 32 位有符号整数计算结果再转回普通数字。也就是说2147483647 1在 JavaScript 里会得出一个负数因为移位后超出了 32 位有符号范围。如果你用 JS 做二进制协议解析不理解这一点会踩到很多坑。另外Go 语言区分有符号和无符号整数的移位Rust 在 debug 模式下移位溢出直接 panic这些言行差异都说明了同一个问题位运算不是“语言无关的语法糖”而是和底层表示强绑定的操作。跨语言迁移时不能只看运算符还要看类型系统。5.4 性能错觉什么时候不该用位运算写代码时经常有人为了“优化”而强行把逻辑改成位运算比如把x % 2改成x 1这没问题但如果你的项目是业务系统数据库查询才是瓶颈位运算省下的那几个纳秒完全可以忽略。而且位运算代码可读性差团队后续维护成本高容易埋下隐藏 bug。合理的取舍是如果操作的是状态集合、权限标志、协议解析、大量循环内的固定模式位运算值得用如果只是偶尔判断奇偶直接用x % 2即可。现代编译器的优化能力很强很多简单的位操作它本身就会自动完成你不需要靠手写位运算来表达意图。注意有位开发者在把业务逻辑“位运算化”时忘了考虑可扩展性。后来系统新增了一个权限维度原来的位标志整个设计就被迫重写。位运算好用但它适合的是“位模式稳定、不频繁扩张”的场景这一点在设计之初就要想清楚。最后分享一个我自己的感悟。很多人学位运算一开始会觉得“会做题就行”但真正让它产生价值的节点是你开始理解二进制是计算机的母语。无论是编译器优化、网络协议解析、数据压缩还是高并发状态管理底层都逃不开位的组合与变换。做算法题时多看几个位运算的经典解法写业务代码时有意识地用掩码组织状态慢慢你会在“人的逻辑”和“机器的逻辑”之间建立一种直觉这种直觉在排查疑难 bug 时尤其好用。如果你正在刷题建议把第 4 节里的几道题手写一遍再对照源码看每一步的位变化胜过刷十道套模板的题。