企业官网建设流程全解析

做算法这几年，我有个很深的体会：位运算就像武侠小说里的内力——平时不显山不露水，但真正遇到硬仗，它往往是最快、最省、最优雅的那把武器。在“优选算法”这个系列里，我想把位运算单独拎出来讲透。原因很简单：它既是面试里高频出现的考点，又是写底层库、做性能优化时绕不开的硬核能力。很多朋友背过&、|、^、~、<<、>>的结论，但一到实战就不知道怎么用；也有人觉得位运算就是炫技，代码可读性差。这两种感觉都正常——位运算的难点从来不是运算符本身，而是缺一套系统化的应用思维。

这篇文章我会从底层电路讲到面试真题，把位运算在算法和工程里的常见用法完整串一遍。你会在力扣、洛谷、AtCoder 上经常看到x & (-x)、n & (n - 1)这类写法，第一次接触确实像天书，但我会逐行拆开，先讲原理，再给可以直接复制的模板，最后把我踩过的坑和面试经验一起整理出来。不管你是准备面试、正在刷题，还是想优化一段性能敏感的业务代码，这篇内容都值得认真看一看。

1. 位运算核心概念：为什么这组底层指令值得单独开一期

1.1 五个基础运算符和一张值得背下来的真值表

先说最基础的东西。位运算操作的对象是二进制位，C/C++、Java、Python、Go 这些主流语言都原生支持。最常用的是五个运算符：按位与&、按位或|、按位异或^、按位取反~、左移<<和右移>>（严谨说是六个）。

一张真值表就能讲完与、或、异或的核心逻辑：

用生活化的方式理解：&是“两边都同意才通过”，|是“只要有一边同意就通过”，^是“两边意见不同才通过”。记住异或这个“不同才为 1”的特征，后面很多奇技淫巧都从它来。

看个具体例子，假设a = 5，二进制是0101；b = 3，二进制是0011：

int a = 5; // 0101 int b = 3; // 0011 a & b // 0001，等于 1 a | b // 0111，等于 7 a ^ b // 0110，等于 6 ~a // 按位取反，对 int 来说结果是 ...11111010 a << 1 // 0101 左移一位变成 1010，等于 10 a >> 1 // 0101 右移一位变成 0010，等于 2

注意~a的结果取决于整数位数，所以直接写成数值没有意义，实际使用时一般用~配合&来做“清除某些位”的操作。左移和右移也很好理解：一位相当于乘 2 和除 2。但这里有个坑——右移对负数的行为在不同语言里并不一致，这一节先按下不表，后面专门展开。

1.2 CPU 为什么偏爱位运算：从电路到编译器的现实

很多人问：位运算快，到底快在哪？核心原因是 CPU 硬件层面就是“由逻辑门构成的”。&、|、^这些操作可以直接映射到与门、或门、异或门上，一个时钟周期内就能出结果；而加法、乘法、除法需要更复杂的电路。加法器本质上也是由一堆逻辑门组合出来的，乘除法更是要占用多个周期甚至专门的单元。

从编译器角度看，现代编译器也经常做这种优化：你写x * 2，它可能直接生成x << 1的指令；你写x / 2，遇到无符号数可能优化成x >> 1。所以从结果上说，位运算在“底层优化”里无处不在。但我也要泼一盆冷水：这不意味着你看到乘除法就该手改成位运算。现代 CPU 的乘除法已经很快，编译器也越来越聪明，为了可读性，业务代码里该写乘除就写乘除。位运算真正的用武之地，是优化算法复杂度、压缩存储、以及做那些乘除法根本做不到的二进制操作。

2. 高频位运算技巧拆解：判断、变换、枚举一次讲清

2.1 十个高频技巧速查表

位运算的实用招式集中在下面这张表里，建议配合代码一起理解：

这几个技巧里，面试和实际编码出现频率最高的是n & (n - 1)和n & (-n)。n & (n - 1)的作用是“把最低位的 1 变成 0”，比如n = 12，二进制1100，n - 1 = 1011，两者相与得到1000，相当于删掉了从右边数第一个 1。这个操作在做汉明重量、判断 2 的幂、枚举子集时反复出现，值得刻进肌肉记忆。

n & (-n)则是“只保留最低位的 1”，比如n = 12，二进制1100，-n = 0100（补码表示），相与后得到0100，也就是只留下了最低位的那个 1。数据结构和算法里大名鼎鼎的树状数组就是靠它实现单点更新和前缀查询的。

2.2 异或的底层身份：可逆、自反，以及“找落单”的经典用法

异或是位运算里最“有性格”的一个。它有两个关键性质：第一个是交换律和结合律，也就是一堆数字互相异或，顺序无所谓；第二个是x ^ x = 0，x ^ 0 = x，自己和自己异或会抵消。这两个性质组合起来，直接诞生了一个经典面试题：一个数组里只有一个数字出现一次，其余数字都出现两次，怎么找出那个落单的数字？

一行代码就能解决：

#include <iostream> #include <vector> using namespace std; int singleNumber(vector<int>& nums) { int ans = 0; for (int x : nums) { ans ^= x; } return ans; } int main() { vector<int> nums = {1, 2, 1, 2, 3, 4, 4}; cout << singleNumber(nums) << endl; // 输出 3 return 0; }

为什么是对的？因为整个数组异或一遍，所有出现两次的数字都会两两抵消成 0，最后剩下的就是那个只出现一次的数字。我第一次看到这个解法时，真有一种“还能这样玩”的震撼。暴力做法需要哈希表，空间 O(n)；排序去重至少要 O(n log n)；而位运算把时间和空间都压到了极致，这就是“优选算法”的意义。

再进阶一点：如果一个数组里有两个数字只出现一次，其余都出现两次，怎么找？思路是：先整体异或，得到两个目标数字的异或值xor_sum；这个值里至少有一个二进制位是 1，找到这个位，把数组分成“该位为 1”和“该位为 0”两组；因为其他数都是成对出现，它们分到同一组也会抵消，最后两组各自异或的结果就是两个目标数。整个过程仍然是 O(n) 时间、O(1) 空间。这是力扣第 260 题的经典做法，建议自己动手写一遍。

2.3 状态压缩：一个整数的二进制位就是一个小型集合

位运算的另一个大杀器是“状态压缩”。如果一个问题的状态只能取“有/无”、“是/否”，并且总数不超过 20 或 30，就可以用一个整数来保存整个状态。这个整数的第 i 位表示“第 i 个元素是否被选中”。

比如集合里有 5 个元素，mask = 19，二进制是10011，就表示选中的是第 0、1、4 个元素。通过位运算，你可以很方便地判断某个元素是否在集合里：mask & (1 << i)；可以添加元素：mask | (1 << i)；可以删除元素：mask & ~(1 << i)。

在状态压缩 DP 里，最常见的场景是枚举子集。假设当前掩码是mask，想枚举它的所有非空子集，标准写法是：

for (int sub = mask; sub > 0; sub = (sub - 1) & mask) { // 处理 sub }

这段代码的精妙之处在于，sub = (sub - 1) & mask会不断从sub中去掉元素，但一直保持在mask内，保证枚举出的 sub 都是 mask 的子集，而且不会重复。我第一次手推这个循环时也愣了半天，核心理解点在于：减 1 操作会把最低位的 1 变成 0，同时让更低位的所有 0 变成 1，再与 mask 相与，就把这些新增的位限制回 mask 允许的范围内。

再往上走，就是状态压缩 DP。以旅行商问题为例，经典状态是dp[mask][i]，表示已经走过mask集合中的城市，当前位于城市 i 的最短路径长度。mask是一个整数，第 k 位表示城市 k 是否已经访问过。相比枚举所有排列，状态压缩 DP 的复杂度从O(n!)降到了O(2^n * n^2)，20 个城市以内的规模完全扛得住。位运算在这里不是锦上添花，而是把不可能变成可能的唯一路径。

3. 位运算的工程价值：从权限管理到海量数据过滤

3.1 权限系统里的“开关组合”

工程里最直观的位运算应用就是权限系统。熟悉 Linux 的同学都知道，文件权限用rwx表示：读是r，对应二进制100，十进制 4；写是w，对应二进制010，十进制 2；执行是x，对应二进制001，十进制 1。chmod 755的含义是：属主有读、写、执行三种权限，即 7；属组有读和执行，没有写，即 5；其他人同样有读和执行，也是 5。

为什么会设计成 4、2、1 而不是 1、2、3？因为这三个数每一个都恰好占一个二进制位，互不重叠，可以同时存储在同一份二进制数据里，而且用位运算就可以自由组合和判断：

const int READ = 0b100; // 4 const int WRITE = 0b010; // 2 const int EXEC = 0b001; // 1 int permission = READ | WRITE; // 0b110，拥有读和写，十进制是 6 bool canRead = (permission & READ) != 0; // true bool canExec = (permission & EXEC) != 0; // false // 增加一个执行权限 permission |= EXEC; // 0b111 // 撤销一个写权限 permission &= ~WRITE; // 0b101

这段代码如果换成三个 bool 变量，逻辑也没错，但位掩码方案有两个明确优势：一是存储极其紧凑，一个 int 就可以表示 32 种独立权限；二是权限的组合、增删、校验都靠几个位运算搞定，性能高，语义也非常清晰。不要觉得只有系统底层才这么干，很多 Web 框架的权限模块、内部系统的功能开关，本质上也是同一套思路。

3.2 Bitmap：一个亿级数据场景的真实容量计算

假设现在有个需求：给你 1 亿个整数（范围在 0 到 1 亿之间），让你快速判断一个数是否出现过，内存限制还很严格。如果用哈希表，光是存储 1 亿个 int 就要大约 400MB，显然不现实。但如果只需要“出现过/没出现过”二值信息，就可以用位图：每一位表示一个数是否存在，1 存在，0 不存在。1 亿个 bit，除以 8 就是 12.5MB，内存少了几十倍，这就是位图的威力。

用一个 int 数组就可以实现简单位图，C 语言风格如下：

#define BITS_PER_INT 32 void set_bit(int bitmap[], int k) { bitmap[k >> 5] |= 1 << (k & 31); } int get_bit(int bitmap[], int k) { return (bitmap[k >> 5] >> (k & 31)) & 1; }

这里的k >> 5相当于k / 32，k & 31相当于k % 32，因为 32 是 2 的幂，所以位运算直接替代了除法。在实际工程里，Java 有现成的BitSet，C++ 标准库有std::bitset，Redis 也提供了 SETBIT/GETBIT 命令，做 UV 统计、在线状态、布隆过滤器时都会用到。

布隆过滤器更是把位图用到了极致：用多个哈希函数把数据映射到位数组的不同位置。查询一个元素时，如果所有位都为 1，就说“可能存在”；一旦发现某个位为 0，那一定是“不存在”。这种结构牺牲了极小的误判率，换来了巨大的空间节省，底层全部是位运算在支撑。

3.3 状态压缩搜索：算法竞赛里不得不解的难题

算法竞赛中有一类问题，朴素搜索的复杂度高到不可接受，但用整数表示状态后，配合 DP 或 BFS 就能瞬间起飞。除了刚才说的 TSP，还有一个很经典的例子：倒水问题、八数码问题、二进制棋盘翻转问题。二进制棋盘翻转经常用mask记录当前哪些位置还是黑色，每次翻转操作就是对 mask 做异或。

我之前做过一道题：给一个 3x3 的棋盘，每个格子黑白两色，点击一个格子会同时翻转它和上下左右四个格子，要求用最少的点击次数把棋盘变成全白。搜索状态可以用一个 9 位的整数表示，0白1黑，翻转操作就是mask ^ (1 << 某个位置)以及周围位置的异或。这样 BFS 的状态判重就是一次哈希表查找，代码写起来非常干净。

这里我想强调的是：位运算在工程和算法里的角色不太一样。工程上，它更多是为了压缩存储、提高单条指令效率；算法上，它是降低“状态表达成本”的关键工具。大部分复杂问题一旦能用整数表示状态，剪枝、记忆化、DP 全都可以顺理成章地套上去。

4. 手把手实操：4道高频位运算题从思路到 AC

4.1 LeetCode 136：只出现一次的数字

刚才在讲异或原理时已经给过代码，这里再补充完整思路。题目要求时间复杂度 O(n)、空间复杂度 O(1)，暴力哈希显然是空间不达标，排序也是时间不达标，唯一自然的解法就是异或。关键理解：异或满足交换律和结合律，所以数组中所有数依次异或，等价于把所有出现两次的数先两两配对抵消，最终剩下的就是答案。

class Solution { public: int singleNumber(vector<int>& nums) { int ans = 0; for (int num : nums) { ans ^= num; } return ans; } };

这个解法建议背下来，不是死记硬背，而是理解“成对抵消”这个思维模型。以后只要看到“一个数组里大部分元素成对出现、只有一个落单”这种描述，第一反应就应该是异或。

4.2 LeetCode 191：位1的个数

题目问一个无符号整数的二进制表示里有多少个 1。最直接的思路是循环检查每一位，但更经典的技巧是利用n & (n - 1)：

class Solution { public: int hammingWeight(uint32_t n) { int count = 0; while (n) { n &= (n - 1); ++count; } return count; } };

循环次数不再固定是 32 次，而是等于二进制中 1 的个数。n & (n - 1)每次都会“清掉最低位的 1”，所以统计完所有 1 之后 n 变成 0，循环自然结束。这道题还有一个变体叫“汉明距离”，就是两个数的二进制差异位数，做法是x ^ y之后统计 1 的个数，本质是同一套底层能力。

4.3 LeetCode 78：子集

给定一个不含重复元素的数组，要求返回所有子集。这道题有很多解法，但位掩码法最直观：数组长度如果是 n，那么每个子集都对应一个 n 位的二进制掩码，掩码的十进制范围是 0 到2^n - 1。

class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { int n = nums.size(); vector<vector<int>> ans; for (int mask = 0; mask < (1 << n); ++mask) { vector<int> cur; for (int i = 0; i < n; ++i) { if (mask & (1 << i)) { cur.push_back(nums[i]); } } ans.push_back(cur); } return ans; } };

外层遍历所有掩码，内层判断每一位是否选中。复杂度是O(n * 2^n)，对于 n 不超过 20 的题目非常稳。这道题让我印象很深的是：第一次写完这个解法，我突然理解了“枚举”在计算机里到底是怎么实现的——一个 for 循环从 0 数到2^n - 1，本质上就是在跑完所有二进制排列，状态压缩的思想在此刻变得异常具体。

4.4 快速幂：位运算在数值计算中的经典体现

最后来个和数值计算强相关的经典算法：快速幂。要求a的b次方对mod取模，如果直接循环乘 b 次，复杂度 O(b)，b 大到 1e9 就直接超时。快速幂的思路是：把 b 看成二进制数，例如b = 13，二进制1101，即13 = 8 + 4 + 1，所以a^13 = a^8 * a^4 * a^1。我们只需要从左到右扫描 b 的二进制位，遇到 1 就把当前累积的幂乘进答案，同时每一步都把底数平方：

long long qpow(long long a, long long b, long long mod) { long long res = 1 % mod; a %= mod; while (b > 0) { if (b & 1) { res = res * a % mod; } a = a * a % mod; b >>= 1; } return res; }

这里b & 1判断当前最低位是不是 1，b >>= 1相当于把 b 的二进制位依次从低位到高位扫一遍。复杂度降为 O(log b)。我当年学快速幂时最大的感慨是：b本身是 10 进制数，但代码里却在“读取”它的二进制结构，位运算在这里真正参与了算法设计，而不只是优化细节。

5. 避坑与面试建议：位运算的边缘地带

5.1 优先级：最容易翻车的隐性坑

位运算最大的坑之一就是运算符优先级。很多语言里，比较运算符的优先级高于位运算的与、或、异或。比如a & b == c在 C/C++ 和 Java 里的解析其实是a & (b == c)，因为==先执行，表达式变成b == c这个布尔值再去和 a 做按位与。几乎每个工程团队都有人踩过这个坑。

再看一个经典例子：1 << 2 + 3。你可能以为先移位再加 3，但实际上+的优先级高于<<，所以它会先算2 + 3 = 5，然后1 << 5 = 32。这种隐蔽错误特别难排查，因为代码编译能过，运行结果也稳定，只是不合法。

我的建议简单粗暴：凡是涉及位运算的表达式，尤其是混合了比较、加减、移位的代码，一律加括号。宁可多写两个括号，也不要赌队友和未来的自己能记住那张优先级表。面试时如果现场手写，加括号还能避免被追问时翻车。

5.2 有符号数与移位陷阱

右移操作在有符号数和无符号数上表现不一样，这是新手最容易忽视的地方。无符号数右移是逻辑右移，高位补 0；有符号数的右移在绝大多数编译器和语言里是算术右移，高位补符号位。也就是说，-8 >> 1的结果是-4，因为它把符号位向右复制了；如果你以为它变成 4，逻辑就完全错了。

Java 里区分得很清楚：>>是带符号右移，>>>是无符号右移；C++ 标准里对有符号数的右移行为是实现定义的，但主流编译器都做算术右移。所以跨平台代码里处理负数右移时，建议先明确你的目标语言行为，再动手写。

另一个坑是左移溢出。一个 int 只有 32 位，1 << 31会变成负数，1 << 32在某些平台上行为不可控。做位掩码时，如果第 k 位可能超过 30，记得用1LL << k转成 long long，避免溢出。还有n << k和n * (1 << k)在不溢出的前提下等价，但一旦溢出，位运算会默默截断，而乘法则可能按更大的类型提升，两者结果可能不同，这也是一个常被忽略的差异点。

5.3 可读性优先：什么时候别用位运算

位运算虽强，但我不建议在业务代码里“无脑位运算”。我曾见过有人把三个布尔状态强行塞进一个 int，然后用&和|判断，理由是不想多写字段。结果三个月后别人接手，代码完全读不懂，还差点改出线上事故。集合操作、状态管理，如果元素数量很小，用数组、Set、布尔字段会更清晰。

我的判断标准是三条：第一，代码是否运行在明确的热点路径上，比如千万级循环内部、内存极受限的嵌入式环境；第二，位运算是否真的能降低算法复杂度或显著减少存储成本；第三，是否有清晰注释说明这个位运算等价于什么逻辑。三条都满足，位运算才是合理选择；否则，可读性优先，让位运算回到它该在的地方。

5.4 面试官真正想看到什么

算法面试里位运算出现频率不低，而且经常以送分题的姿态出现。面试官考察的其实不是你会不会背公式，而是两点：第一，能不能识别出“这道题该用位运算”；第二，能不能把位运算背后的数学性质讲清楚。比如，看到“只出现一次”想到异或，看到“子集”“状态”想到掩码，看到“海量存在性判断”想到位图，这些都属于识别能力。

讲思路时，我建议你像这样组织：先说明朴素解法的复杂度，再指出位运算为什么能优化。比如“这道题暴力开哈希表是 O(n) 空间，但如果用异或，因为异或满足自反性，成对数字会抵消，所以空间降到 O(1)”。这比背代码要有说服力得多。

练习资源的建议：力扣的“位运算”标签下题目，按通过率从高到低刷；LeetCode 136、191、260、78、201、371 都是很好的载体；CSES 的 Mathematics 部分也有位运算相关题目，可以练英文阅读和基础功底。刷题时多问自己一步：这题如果不用位运算，还能不能做？比原题复杂在哪里？想明白这一点，位运算才算真正内化。

最后说一点个人体会。我现在写位运算代码依然保留一个原则：先写清楚，再谈优化。凡是位运算表达式，一律加括号；凡是能用可读写法表达的普通场景，绝不为炫技换位运算；凡是留在性能热点里的位运算，都会配一行注释说明它等价于什么数学操作。这个习惯帮我少踩了很多坑。你可以顺着这篇文章的目录，把每段代码在自己机器上敲一遍，再去做力扣“位运算”标签下的前二十题，很快就能体会到：内力的提升，往往就在这些朴实无华的位之间。