说起“位运算”，很多人脑袋里浮现的第一行代码可能是n & 1 == 1或者一个^用在交换两数上。但在真实项目和算法比赛里，位运算的价值远不止面试炫技——它是少数几种“从底层逻辑上解决问题”的工具：状态压缩、权限校验、布隆过滤器、嵌入式寄存器操作，哪一样都离不开它。这篇文章就围绕“常见位运算”这一主题，把基本的运算符、高频套路、真实场景和防坑经验一次性梳理清楚，适合正在刷算法题的学生、写业务代码想优化性能的工程师，以及需要跟底层硬件打交道的开发者。我会尽量用大白话拆解原理，同时给出一看就能用的代码和踩坑记录。

1. 位运算的基本盘：四个运算符加两种移位

1.1 一张真值表讲清按位与、或、异或、取反

位运算操作的是二进制位，也就是每个比特位上的 0 或 1。按位与（&）、按位或（|）、按位异或（^）、按位取反（~）是最基础的四个操作，其实它们各自的规则用一句话就能说明白：

• 与（&）：两个位都是 1 才是 1，否则是 0。类似于“两个条件同时满足才成立”。
• 或（|）：两个位只要有一个是 1 就是 1，否则是 0。类似于“至少一个满足就成立”。
• 异或（^）：两个位不相同为 1，相同为 0。它的核心含义是“找不同”。
• 取反（~）：0 变 1，1 变 0，即按位翻转。

大部分入门材料会用一张真值表把A & B、A | B、A ^ B的存在关系列出来，但我觉得真正实用的做法是把它们“翻译”成逻辑判断，方便在写代码时快速反应：

假设A = 5，二进制为101；B = 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 % 2：

if (n & 1) { // n 是奇数 } else { // n 是偶数 }

这里要注意：&的优先级比==低，所以写n & 1 == 1实际上会被解析成n & （1 == 1），结果就错了。正确写法是if (n & 1)或显式加括号if ((n & 1) == 1)。

我见过不少人在循环里用n % 2判断奇偶，这当然没错，但在追求极致性能的地底层代码里，n & 1确实会有可观测的差距。更重要的是，这一个细节能让你在大规模状态遍历时省掉不必要的模运算开销。

2.2 干掉最低位 1：n & (n - 1) 和 lowbit

n & (n - 1)是位运算里最经典的一行代码，作用是“将 n 的二进制表示中最右边的 1 变成 0”。这个操作能做的事太多了：

• 判断 2 的幂：如果n > 0且n & (n - 1) == 0，那么 n 就是 2 的幂。
• 统计 1 的个数：不断执行n &= (n - 1)，每执行一次消掉一个 1，计数加 1，直到 n 变成 0。
• 组合枚举：遍历状态子集。

与它配套的还有一个lowbit技巧，也就是取到二进制中最右边的 1：

lowbit(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(vector<int>& 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 开始计数），可以这样构造掩码：

• 置为 1：x |= (1 << k)
• 清零：x &= ~(1 << k)
• 翻转：x ^= (1 << k)
• 查询：(x >> k) & 1

这套操作可以被组合成非常优雅的“位图”（bitmap）。假设你有一组 id，范围在 0 到 31 之间，你想记录哪些 id 已经出现过，那么一个 32 位的整数就够了。

int bitmap = 0; // 插入 id=3 bitmap |= (1 << 3); // 判断 id=3 是否存在 if ((bitmap >> 3) & 1) { /* exist */ } // 删除 id=3 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 中移除城市 j：S ^= (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 这样的数，二进制是1010，10 - 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。

vector<int> findTwoSingle(vector<int>& 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 = 0，x ^ 0 - 0 = x；如果 x 是负数，sign = -1（全 1），x ^ (-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_cast<uint32_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 & 0xffffffff

JavaScript 更特殊，它的位运算先把操作数转成 32 位有符号整数，计算结果再转回普通数字。也就是说2147483647 << 1在 JavaScript 里会得出一个负数，因为移位后超出了 32 位有符号范围。如果你用 JS 做二进制协议解析，不理解这一点会踩到很多坑。

另外，Go 语言区分有符号和无符号整数的移位，Rust 在 debug 模式下移位溢出直接 panic，这些言行差异都说明了同一个问题：位运算不是“语言无关的语法糖”，而是和底层表示强绑定的操作。跨语言迁移时，不能只看运算符，还要看类型系统。

5.4 性能错觉：什么时候不该用位运算

写代码时经常有人为了“优化”而强行把逻辑改成位运算，比如把x % 2改成x & 1，这没问题；但如果你的项目是业务系统，数据库查询才是瓶颈，位运算省下的那几个纳秒完全可以忽略。而且位运算代码可读性差，团队后续维护成本高，容易埋下隐藏 bug。

合理的取舍是：如果操作的是状态集合、权限标志、协议解析、大量循环内的固定模式，位运算值得用；如果只是偶尔判断奇偶，直接用x % 2即可。现代编译器的优化能力很强，很多简单的位操作它本身就会自动完成，你不需要靠手写位运算来表达意图。

注意：有位开发者在把业务逻辑“位运算化”时，忘了考虑可扩展性。后来系统新增了一个权限维度，原来的位标志整个设计就被迫重写。位运算好用，但它适合的是“位模式稳定、不频繁扩张”的场景，这一点在设计之初就要想清楚。

最后分享一个我自己的感悟。很多人学位运算，一开始会觉得“会做题就行”，但真正让它产生价值的节点，是你开始理解二进制是计算机的母语。无论是编译器优化、网络协议解析、数据压缩还是高并发状态管理，底层都逃不开位的组合与变换。做算法题时多看几个位运算的经典解法，写业务代码时有意识地用掩码组织状态，慢慢你会在“人的逻辑”和“机器的逻辑”之间建立一种直觉，这种直觉在排查疑难 bug 时尤其好用。如果你正在刷题，建议把第 4 节里的几道题手写一遍，再对照源码看每一步的位变化，胜过刷十道套模板的题。