企业官网建设流程全解析

前两天在改一段状态枚举的性能瓶颈代码，朋友问我：为什么他写的判重逻辑比我慢好几个量级。我扫了一眼，发现他用了一个数组去存所有已访问的组合，每次查找都要线性扫描。我跟他说：把一个集合压进一个整数里，一行位运算就能判定包含关系。他把那段改成位掩码之后，整个程序从秒级掉到毫秒级。

位运算这个东西，看起来只是& | ^ ~ << >>六个运算符，但真正用熟了以后，你会发现它能干的事远超“快一点点”这个层面：状态压缩、集合运算、权限控制、协议解析、哈希混合、算法剪枝，背后全都能用位运算一把梭。这篇文章整理了30个我在实际项目和刷题过程中验证过的位运算实战技巧，每个都给出可落地的写法、背后的原理和容易踩的坑。适合正在学算法的学生、写底层或嵌入式代码的工程师，以及任何想提升代码性能的开发者。

1. 位运算基础：先建立位级直觉

1.1 原码、反码、补码：别跳过，这里决定你是否踩坑

很多位运算技巧，尤其是负数相关的，看不懂的根本原因是没有真正理解补码。拿8位整数举例：1的原码是00000001，-1在计算机里并不是10000001，而是11111111，也就是所谓的补码。补码的计算方法是取反加一：1取反得到11111110，再加一得到11111111。

为什么计算机要用补码？一个核心原因是让加减法统一。5 + (-3)在补码表示下直接按二进制加法算就能得出正确结果，不需要额外的减法器。这个设计直接衍生出了一个位运算里最常用的公式：x & -x能提取最低位的1。后面的技巧15会细说，但你现在只要记住：负数的二进制表示，决定了~x + 1 == -x。

理解了这一点，你就知道为什么x >> 31在C语言里对一个32位int来说，正数得到0，负数得到0xFFFFFFFF。这个性质被大量用在“根据正负生成掩码”的技巧里。

1.2 六个常用运算符：一张表看清行为

异或是这里面最特殊的一个，它的三个性质一定要刻在脑子里：a ^ 0 = a，a ^ a = 0，异或满足交换律和结合律。这意味着你可以用异或做“无进位加法”、做“出现偶数次就抵消”的统计、做“不引入第三个变量”的交换。后面会大量用到。

1.3 为什么位运算快：从硬件层面看本质

位运算快不是因为“大家都这么说”，而是因为CPU里每一个位运算都对应一组简单的逻辑门电路。加法器需要考虑进位链，乘法器更是要多次移位累加，而一个AND或OR在晶体管层面就是几个MOS管的组合，延迟极低，通常一个时钟周期内就能完成。

不过我也得说句实话：在现代编译器面前，很多位运算技巧不见得比普通写法快，比如x % 2和x & 1在开启优化后生成的汇编常常是一样的。那学这些技巧还有什么用？真正的价值在于三点：一是表示能力，一个int能当一整个集合用，这是普通写法很难替代的；二是协议和底层开发里，二进制格式本来就是位级的，不会位运算根本做不了事；三是算法层面，状态压缩DP、N皇后剪枝这类场景，位运算能让复杂度的常数项大幅下降。所以这篇文章里的技巧，不要只当作“炫技”，要当作一种思维方式来学。

2. 状态压缩与位掩码：用一个整数表示一组开关

2.1 技巧1：权限控制的经典位掩码

如果你写过带权限的系统，一定见过类似READ = 1, WRITE = 2, EXEC = 4的定义。这三个权限分别对应二进制的第0位、第1位、第2位，用一个整数就能保存所有权限的任意组合。

#define READ (1 << 0) #define WRITE (1 << 1) #define EXEC (1 << 2) int perm = READ | WRITE; // 0b011，拥有读和写 if (perm & WRITE) { /* 可以写 */ } perm |= EXEC; // 加执行权限，变成0b111 perm &= ~WRITE; // 去掉写权限，变成0b101 perm ^= READ; // 翻转读权限，变成0b100

这个模式我在实际项目里用过不止一次，性能和可扩展性都很好。唯一要注意的是，新加权限位时只能选择尚未使用的比特位，不能随手定义成3或5，因为3 = 0b11会同时占用读和写两个位，导致判断混乱。

2.2 技巧2：枚举一个集合的全部子集

假设你有一个集合mask = 0b1011，想枚举它的所有非空子集，最优雅的写法是：

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

我当年第一次看到这个循环时很震撼：sub - 1会把最低位的1变成0，并把更低位全部变成1，再和mask取与，就保证了结果始终是mask的子集，且不重不漏。例如mask = 0b1011，枚举顺序是1011, 1010, 1001, 1000, 0011, 0010, 0001。如果你想包含空集，循环结束后单独处理sub = 0即可。

这个技巧在状态压缩动态规划里出现频率极高。比如“给出一堆物品，选若干件凑出某个目标”，或者“从一个集合的子集中找最优解”，直接枚举子集可以省去大量递归搜索的时间。

2.3 技巧3：集合运算三件套：包含、交、并、差

当集合元素个数不超过机器位数时，一个int就是一个完美的集合：第i位为1表示元素i在集合中。

• 判断b是否是a的子集：(a & b) == b
• 判断a和b是否有交集：(a & b) != 0
• 求并集：a | b
• 求差集：a & ~b

看到没有，所有集合运算都变成了一次位运算。我曾经在写定时任务调度器时，用一个int weekdayMask表示一周七天里哪些天需要执行任务：工作日 = 0b0011111，周六 =0b0100000，判断某天是否工作日只要weekdayMask & (1 << dayIndex)。这段代码比任何数组遍历都直观，而且可读性极强。

2.4 技巧4：用位数组做海量数据存在性初筛

处理海量数据时，我们经常需要快速判断“某个数之前是否出现过”。如果直接开一个bool数组，数据范围一大就爆内存。这时候可以用bitset思想：用一个long数组，第i个long保存第64*i到64*i+63位的标记。

unsigned long bits[N / 64 + 1]; // 设置第x位 bits[x >> 6] |= 1UL << (x & 63); // 查询第x位 if (bits[x >> 6] & (1UL << (x & 63))) { /* 存在 */ }

x >> 6相当于x / 64，x & 63相当于x % 64，这里用位运算纯粹是为了效率。这是布隆过滤器、爬虫去重、海量数据排序等场景的基石。如果你用的是Python，int天然就是无限长的bit数组，直接通过|=和&操作即可，调试起来非常方便。

2.5 技巧5：状态DP中的位压缩

状态压缩动态规划可能是位运算在算法竞赛里最重要的应用。经典例子是旅行商问题：dp[mask][i]表示已经访问过mask中的城市、当前位于城市i的最短路径。这里的mask就是一个整数，比如0b10101表示城市0、2、4已经被访问。

状态转移时，尝试从城市i走到还没有访问过的城市j：

if (!(mask & (1 << j))) { int nextMask = mask | (1 << j); dp[nextMask][j] = min(dp[nextMask][j], dp[mask][i] + dist[i][j]); }

用位运算判断“城市j是否访问过”、标记“城市j已访问”，代码不仅短，而且运行速度极快。如果城市数量超过60，就需要用多个整数拼起来，或者直接用Python的无限位整数。我个人的建议是，状态压缩DP值得专门花时间练，因为它强迫你把“集合”这个概念在脑内和“整数”建立映射。

3. 二进制奇技淫巧：让代码更短更高效

3.1 技巧6：判断一个正整数是否是2的幂

判断一个正整数x是不是2的幂，传统写法可能是用循环不断除以2。位运算一行搞定：

int isPowerOfTwo(int x) { return x > 0 && (x & (x - 1)) == 0; }

原理是：一个2的幂的二进制表示只有一个1，比如8 = 0b1000，减去1后变成0b0111，两者相与必然为0。如果x里有多个1，比如10 = 0b1010，减1后是0b1001，相与后得到0b1000，不为0。注意要排除x = 0，因为0的二进制没有1，0 & -1 = 0，但不满足“正整数”的语义。

3.2 技巧7：统计二进制中1的个数

统计二进制里有多少个1，是面试高频题。布赖恩·克尼根算法很经典：

int count = 0; while (x) { x &= x - 1; // 每次都消掉最低位的1 count++; }

x & (x - 1)这个表达式的作用是“把最低位的1变成0”，所以循环次数等于1的个数，而不是固定的32次。如果你想追求极致性能，现代CPU和编译器基本都提供了内置函数：C++用__builtin_popcount，Java用Integer.bitCount。但自己写一遍有助于理解位运算的底层逻辑，而且这个技巧经常和“判断2的幂”“计算奇偶校验”联动出现。

3.3 技巧8：交换两个变量而不借助临时变量

这是一个经典到被说烂的技巧：

a ^= b; b ^= a; a ^= b;

原理是利用异或的自反性：a ^ b ^ b = a。第一步后a保存了a ^ b，第二步让b变成(a ^ b) ^ b = a，第三步让a变成(a ^ b) ^ a = b。三步之后，两人完成交换。

我必须提醒一句：在实际工程里，这个技巧并不比tmp = a; a = b; b = tmp;更快，因为编译器对临时变量交换的优化已经很成熟。它更大的价值是加深对异或的理解。除非你在写某些寄存器操作或硬件代码、确实没有额外寄存器可用，否则不必刻意用。

3.4 技巧9：取绝对值

位运算版的绝对值长这样：

int abs(int x) { int mask = x >> 31; // 正数为0，负数为全1 return (x + mask) ^ mask; // 等价于 (x ^ mask) - mask }

如果x是非负数，mask是0，结果就是x。如果x是负数，比如-5，mask = 0xFFFFFFFF，x + mask = -5 - 1 = -6，-6 ^ 0xFFFFFFFF = 5。这个写法背后就是负数取绝对值的补码运算：先减1，再按位取反。

实际开发中我建议直接用abs或Math.abs，可读性高得多。这个技巧的用途更多是理解位级处理，以及在某些不允许调用库函数的底层环境里实现。有一个大坑必须记牢：INT_MIN的绝对值是INT_MIN本身，因为它的补码没有对应的正数表示，直接算会溢出。

3.5 技巧10：判断奇偶

x & 1是基于二进制最低位来判断奇偶的：最低位为1就是奇数，为0就是偶数。

if (x & 1) { /* 奇数 */ } else { /* 偶数 */ }

业务代码里，我还是推荐写x % 2，因为可读性更好。但在性能敏感的内层循环里，x & 1生成的指令可以少一两条，对于几十亿次迭代的循环能省下不少时间。另外，有些老代码里会用!(x & 1)判断偶数，看到的时候心里要清楚它在干什么。

3.6 技巧11：模2的幂优化

当模数是2的幂时，x % m可以写成x & (m - 1)：

x % 64 等价于 x & 63 x % 256 等价于 x & 255

这个技巧在哈希表设计里极其重要。经典做法是把哈希桶数量设置成2的幂，然后用hash & (cap - 1)计算桶下标，替代取模运算，速度更快。这也是为什么很多哈希表扩容时总是把容量设计成16、32、64这种数字。

但要注意一个细节：在C/C++里，如果x是负数，x % 64的结果可能是负数（在C11前实现定义，通常为负数），而x & 63结果是非负的。两者语义不同，不能无条件替换。Java里Math.floorMod和位运算的差异也需要注意。所以这个优化只适合“你明确知道x非负”或“你就是要二进制低位”的场景。

3.7 技巧12：无分支地求两个数的最小值

传统写法min = a < b ? a : b在现代CPU上已经有了cmov指令，性能不差。但位运算版本可以帮你理解“用掩码做选择”的思想：

int min = b ^ ((a ^ b) & -(a < b));

如果a < b为真，-(a < b)生成全1掩码，(a ^ b) & 全1等于a ^ b，于是结果变成b ^ (a ^ b) = a。如果a < b为假，掩码全0，结果就是b。本质上是用位运算模拟了一个条件选择器。这个思路在后续很多高级技巧里都能复用：用运算结果构造掩码，再通过掩码选择两路数据。

3.8 技巧13：lowbit：提取最低位的1

x & -x可能是整个位运算体系里最有价值的一个表达式。

int lowbit(int x) { return x & -x; }

以x = 12 = 0b1100为例，-x的补码表示是0b0100，两者相与得到0b0100，也就是4，刚好是12的最低一个1所在位的权重。这个操作之所以有用，是因为x & -x可以直接定位到二进制中最靠右的1。

lowbit最常见的应用是树状数组的更新和查询：

void add(int idx, int delta) { while (idx <= n) { tree[idx] += delta; idx += idx & -idx; } }

另一个用途是遍历一个整数的所有置位：

while (x) { int lb = x & -x; // 处理lb x -= lb; }

3.9 技巧14：找最右侧的0的位置

有时候你要找的不是最低位的1，而是最低位的0，比如在一个位分配器里找第一个空闲槽位：

int rightmostZero = ~x & (x + 1);

这个表达式的原理是：x + 1会让最低位的0变成1，同时它右边的所有1（如果有）都进位变成0。与~x相与后，刚好留下那个原本为0的位。比如x = 0b10101111，x + 1 = 0b10110000，~x = 0b01010000，相与得到0b00010000。

这个技巧在资源管理、内存池分配、位图分配器里很实用。需要留神的是，如果x全为1，~x & (x + 1)会得到0，这时表示没有空闲位。

4. 图论与数据结构里的位压缩

4.1 技巧15：用bit表示的邻接矩阵做高效判断

图论里，邻接矩阵通常用二维数组存，判断两个点是否相邻是O(1)。但如果把每一行邻接信息压成一个整数或bitset，就能一次判断“一个点能否通过某个中间点到达另一个点”。

比如判断是否存在i -> k -> j这样一条两步路径：

if ((adj[i] & adj[k]) != 0) { // 存在某个点j，使得i能到j且k能到j？不，这里要稍微理清 }

更准确的用法是：用adjFrom[i]表示从i出发能到达的所有点的集合，那么adjFrom[i] & adjFrom[k]表示“既可以从i到达、也可以从k到达”的点集。如果想判断能否两步从i到j，就枚举中间点k，看adjFrom[k]里是否包含j，同时用adjFrom[i]判断i是否能到k。配合bitset，对稠密图的多源可达性计算能大幅提速。

这种“一个整数就是一行邻接表”的写法，在竞赛里非常香。C++有标准库bitset，Python可以直接用整数，配合&、|操作，代码既短又容易验证。

4.2 技巧16：棋盘状态压缩：用整数表示行、列、对角线

八皇后问题是我最喜欢用来讲位运算的题目。常见的数组写法需要三个布尔数组记录列和两条对角线的占用情况，而位运算版本只需要三个整数。

void dfs(int row, int cols, int diag1, int diag2) { if (row == n) { count++; return; } int avail = ~(cols | diag1 | diag2) & ((1 << n) - 1); while (avail) { int pos = avail & -avail; // 选一个可放皇后的位置 avail -= pos; dfs(row + 1, cols | pos, (diag1 | pos) << 1, (diag2 | pos) >> 1); } }

cols记录哪些列已经有皇后，diag1表示主对角线方向，diag2表示副对角线方向。每次递归时，avail直接算出当前行所有合法位置，不需要循环检查每一列是否冲突。这个版本的八皇后求解速度比数组版本快好几个量级，因为剪枝是在位级上天然完成的。

数独、五子棋棋盘类问题也可以用类似思路：把每一行、每一列、每个宫的状态压成整数，判断某个数字能否填入某个位置就变成了位运算的包含判断。建议找一个经典搜索题自己实现一遍，位运算在搜索剪枝里的价值必须亲手写一次才有体感。

4.3 技巧17：集合求交、并、补的高效写法

前面提到过，一个int可以是一个集合。这里展开举一个业务例子：假设你有7个bit表示一周，第0位是周一，第6位是周日。那么“工作日”可以定义为0b0011111，周末是0b1100000。

• 判断某天d是不是工作日：(weekdayMask & (1 << d)) != 0
• 如果把周末也加进去：weekdayMask | weekendMask
• 求非工作日：~(weekdayMask) & 0x7F，注意这里必须与0x7F取与，把7位之外的Bit清掉

第3行特别值得强调：~weekdayMask在C语言里是32位全1的反码，直接拿去用会包含第7位到第31位的垃圾数据。所以求补集时，一定要用一个掩码把有效位宽限制住。这个习惯在你看别人代码时也要保持警觉，很多人写~a后就当结果只包含低7位，这是隐蔽的bug来源。

4.4 技巧18：BFS/DFS状态访问标记

有些搜索题，状态不是单纯的坐标，而是“哪些物品已经取走”“哪些灯已经打开”“哪些格子已经变色”这类组合。这时候二维bool数组就不好使了，因为状态空间是组合爆炸级的。解决办法是把整个状态编码成一个整数，丢进visited集合里。

比如某个谜题有20个开关，每个开关的状态是0或1，可以把所有开关状态拼成一个20位整数。每次操作翻转某个开关时：

state ^= (1 << k); // 翻转第k个开关 if (!visited.count(state)) { visited.insert(state); }

位运算在这里的作用不只是提速，而是让“状态的生成和比较”变得直接、无歧义。用数组去表示一个复杂状态，还要考虑哈希函数怎么设计；用一个整数，哈希就是它本身。

4.5 技巧19：N皇后位运算剪枝的进一步分析

很多人第一次接触位运算剪枝时，会被(diag1 | pos) << 1这种递归参数搞晕。我拆开讲：diag1表示当前行所有被“主对角线”方向占用的列集合。当你在当前行第pos位放一个皇后后，对下一行来说，这个皇后的主对角线影响会向左移动一格（如果把左上到右下视为一条方向），所以左移一位；副对角线影响则右移一位。通过不断移动，就可以用固定位宽的整数记录整个棋盘的对角线冲突。

这个技巧的本质，是把“斜线上的冲突”也当成位集合来维护。对比一下数组写法每次递归要重新检查整行所有位置，位运算版本只做几次| << >> & ~就完成了所有合法性判断。我说实话，第一次手写这个代码时我盯着avail = ~(...) & mask看了半天，但一旦理解，你的搜索类代码功力会直线上升。

5. 编码、哈希与系统底层位技巧

5.1 技巧20：手工实现一个布隆过滤器

布隆过滤器是一种概率性数据结构，底层就是一个位数组加上若干哈希函数。插入时把k个哈希值对应的位置置1，查询时检查k个位置是否全部为1。位运算在这里不只是优化，而是结构本身：

#define BIT_SIZE (1 << 16) #define MASK (BIT_SIZE - 1) unsigned char bits[BIT_SIZE / 8]; void setBit(int h) { bits[h >> 3] |= 1 << (h & 7); } bool testBit(int h) { return bits[h >> 3] & (1 << (h & 7)); }

h & 7因为8是2的幂，所以可以这样取模。哈希函数可以用两个不同的种子跑同一个快速哈希，生成k个位置。布隆过滤器在爬虫URL去重、黑名单过滤、缓存穿透防护里非常常见。它最大的价值是用极小的内存代价换一个“可能误判但绝不漏报”的答案。

5.2 技巧21：快速散列与位混合

写哈希表时，最怕输入数据的低几位高度重复。比如内存地址经常是8字节对齐的，低3位永远是0；再比如字符串哈希以后，低比特可能分布不好。一个经典解法是“位混合”：把高位的信息通过异或和位移搅到低位来。

我常推荐的分裂混合64是这样做的：

x ^= x >> 30; x *= 0xbf58476d1ce4e5b9ULL; x ^= x >> 27; x *= 0x94d049bb133111ebULL; x ^= x >> 31;

每一步的逻辑是：先用右移把高位移到低处，再用异或让高位的模式影响低位；接着用一个大质数乘法把映射关系彻底打乱；最后再右移异或一次，保证每个输出位都依赖多个输入位。这套操作在伪随机数生成器和哈希表扩容里都能看到影子。

5.3 技巧22：字节序与打包/解包

你在分析一个网络协议或者二进制文件格式时，经常需要把4个字节拼成一个整数，或者反过来把整数拆成字节。位运算是这个场景的标配：

// 打包成32位整数（大端） unsigned int pack(unsigned char b0, b1, b2, b3) { return (b0 << 24) | (b1 << 16) | (b2 << 8) | b3; } // 解包 unsigned char b0 = (x >> 24) & 0xff; unsigned char b1 = (x >> 16) & 0xff; unsigned char b2 = (x >> 8) & 0xff; unsigned char b3 = x & 0xff;

解包时必须加& 0xff，否则右移出来的高位会被符号扩展填满。这种“位字段”操作在嵌入式里尤其多：一个32位寄存器，可能低2位是模式、中间10位是阈值、最高位是使能标志，全部用宏定义加&、|、>>来读写。

5.4 技巧23：哈希扰动中的^和>>>

Java的HashMap里有一个经典操作：计算完对象的原始哈希后，再做一次扰动：

int h = key.hashCode(); h ^= (h >>> 16);

为什么要这样做？因为当哈希表容量比较小时，计算桶下标只用得到低几位，比如容量16时只看低4位。如果原始哈希的低4位分布很差，碰撞就很多。h >>> 16把高16位移到低位，再和自己异或，相当于让高位的特征也参与低位的计算。这个技巧的本质是“信息扩散”，和技巧21是同一个思想的轻量版。

我自己在写自定义哈希函数时，也会按照这个思路：先让输入的所有位尽可能互相影响，再进入取模环节。有时候只加一行x ^= x >> something，哈希分布就能显著改善。

5.5 技巧24：奇偶校验

奇偶校验位用于检测数据在传输过程中是否发生单比特翻转。实现方式有很多，最简单的是不停地消去最低位1并翻转结果：

int parity = 0; while (x) { parity ^= 1; x &= x - 1; }

更快的版本用“折叠异或”一次算完：

x ^= x >> 32; x ^= x >> 16; x ^= x >> 8; x ^= x >> 4; x ^= x >> 2; x ^= x >> 1; parity = x & 1;

折叠异或的思路是：把二进制的高半区折叠到低半区，不断进行，直到所有位的信息都集中到最低位。这个写法在课程设计、通信协议和早期存储校验里都很有用。现在的CRC和哈希校验更强大，但奇偶校验的位运算写法值得掌握，因为它一次性展示了“低位折叠”这个通用套路。

5.6 技巧25：按位掩码快速提取/合并字段

有时候你不想写一个结构体，想在一个整数里直接塞多个字段。比如一个32位状态字：高8位保存type，低24位保存id。

#define TYPE_MASK 0xFF000000 #define ID_MASK 0x00FFFFFF int state = (type << 24) | id; int type = (state & TYPE_MASK) >> 24; int id = state & ID_MASK;

这个写法在协议包头、设备寄存器、游戏存档压缩里很常见。它能减少内存占用，还能让整个状态的比较变成一个整数比较，比如if (state == expected)。但代价是可读性下降，所以我建议用宏或者常量把掩码命名清楚，不要到处写魔法数字。另外，字段修改时不要用state = type << 24 | id这种重新构造的方式，而应该先清位再置位：

state = (state & ~TYPE_MASK) | (newType << 24);

5.7 技巧26：二进制逆序技术

把一个整数的二进制位完全倒过来是一个看起来冷门、实际藏在很多算法底层的小工具。经典的“分治法”写法如下：

x = (x & 0x55555555) << 1 | (x >> 1) & 0x55555555; x = (x & 0x33333333) << 2 | (x >> 2) & 0x33333333; x = (x & 0x0F0F0F0F) << 4 | (x >> 4) & 0x0F0F0F0F; x = (x & 0x00FF00FF) << 8 | (x >> 8) & 0x00FF00FF; x = (x & 0x0000FFFF) << 16 | (x >> 16) & 0x0000FFFF;

这段代码每行都在做一件事：把相邻的1位交换，然后再把相邻的2位交换，接着4位、8位、16位。执行完五轮，整个32位整数已经倒过来了。你可以把它类比成归并排序的逆过程：先处理最小块，再不断把块扩大。这个技巧在FFT的位逆序重排、CRC计算、某些图像处理算法里都有应用。理解它不为别的，就为体会“分治思想如何在位级落地”。

6. 数学与逻辑题中的位运算进阶

6.1 技巧27：不用加减乘除做加法

面试题里有道常客：实现两个整数相加，但不准用+和-。位运算解法如下：

int add(int a, int b) { while (b) { int carry = (a & b) << 1; a = a ^ b; b = carry; } return a; }

a ^ b得到的是不考虑进位的加法结果，(a & b) << 1得到的是所有需要进位的位。把这两个结果相加，就是真正的和，而“相加”这个动作又可以用同样的方式递归下去，直到进位为0。这就是硬件加法器的工作原理——全加器就是不断计算“和”与“进位”，只不过硬件是用逻辑门并行实现的。

我当年第一次写这个函数时，觉得它像魔法。后来想明白了：所谓加法，本质上就是异或和进位的反复作用，这个视角对理解计算机组成原理特别有帮助。

6.2 技巧28：格雷码的快速生成与解码

格雷码的特点是相邻两个数值的二进制表示只有一位不同，广泛应用于旋转变压器、编码器、MIMO系统和状态机的防毛刺设计。它的生成公式优雅到不像话：

gray = n ^ (n >> 1);

比如n从0到7，得到的格雷码是000, 001, 011, 010, 110, 111, 101, 100，每相邻两个确实只差1位。解码也简单，从高位往低位逐位异或：

int decoded = gray; while (gray >>= 1) { decoded ^= gray; }

或者更快的方式：

decoded ^= decoded >> 16; decoded ^= decoded >> 8; decoded ^= decoded >> 4; decoded ^= decoded >> 2; decoded ^= decoded >> 1;

这个技巧不是日常开发天天用，但在底层编码和数字电路相关项目里价值很高。就算用不到，理解n ^ (n >> 1)为什么能做到“相邻只有一位不同”，也是一次很好的位级思维训练。

6.3 技巧29：找出只出现一次的数字

一个很经典的题：数组里只有一个数字出现一次，其他数字都出现两次，找出那个唯一的数。解法是把所有数字异或起来：

int res = 0; for (int v : nums) res ^= v; return res;

原理很简单：a ^ a = 0让所有成对出现的数字相互抵消，0 ^ x = x让唯一的数字留下来。这个解法既不需要哈希表，也不需要排序，时间和空间都最优。

我当时第一次看到这个解法时，第一反应是“这也太赖皮了”，第二反应是“异或的性质原来可以这么用”。它告诉你一件事：当题目里出现“成对出现”“只出现一次”这类词时，异或往往是隐藏的正解。

6.4 技巧30：找两个只出现一次的数字

把问题升级：数组里有两个数字只出现一次，其余都是两次，怎么找？

int diff = 0; for (int v : nums) diff ^= v; // diff = a ^ b int lb = diff & -diff; // 最低位的1，表示a和b在这一位不同 int a = 0, b = 0; for (int v : nums) { if (v & lb) a ^= v; else b ^= v; }

思路的精髓在于：diff是a ^ b，它二进制中任何一个为1的位，都说明a和b在这一位不同。用这个位把所有数字分成两组，两个只出现一次的数字必然被分到不同组，每组内部再异或一次，就能分别得到它们。这个解法把技巧13的lowbit用到了极致，是位运算综合运用的典范。

7. 避坑指南与调试心得

7.1 运算符优先级：最大的坑没有之一

C语言里面，&、^、|的优先级都低于==和!=。这意味着

if (x & 1 == 0) { ... }

实际会被解析成

if (x & (1 == 0)) { ... }

也就是x & 0，整个条件永远为假。这个问题我在代码评审里见过无数次。Java和Python的优先级规则也各有不同，但结论只有一个：位运算比你想的优先级低，凡是混合使用的场景，一律加括号，不要吝啬那几行空白。

7.2 位移位数和符号扩展陷阱

移位操作有几个容易忽略的规矩。第一，移位数不能大于等于操作数的位宽，否则在C/C++里是未定义行为，在Java等语言里会按低5位或低6位处理，跨语言行为并不一致。第二，左移可能改变符号位，比如0x7FFFFFFF << 1会变成0xFFFFFFFE，这是负数。第三，右移有算术右移和逻辑右移的区别：有符号数大多数情况下是算术右移，空出的高位补符号位；无符号数则是逻辑右移，空出的高位补0。

假设你写int x = -8; x >> 1，很多新手以为结果是4，实际上大多数环境里结果是-4，因为右移补进来的是符号位的1。想确认平台行为，最可靠的方法是自己写一小段代码跑一下，再打印二进制结果，不要凭感觉。

7.3 Python的无限位整数是个双刃剑

Python用户会碰上一个特别反直觉的点：~x在Python里不是“当前机器位宽下取反”，而是“数学意义下的取反”。比如~5得到-6，对应的是无限位补码。这在做底层位模拟时会带来很多意外：

x = 0b1100 print(bin(~x)) # -0b1101，而不是0b...0011 print(bin((~x) & 0xff)) # 0b11110011，这才是8位取反

所以如果你是在用Python模拟C语言的行为，千万不要忘了在每个~运算后用& mask把结果限制到指定位宽。同理，右移负数时Python和C的行为也完全不同，跨语言移植位运算代码时一定要逐个函数验证。

7.4 调试技巧：把二进制打印出来

位运算调试的口诀是：眼算不如打印。我建议在开发环境里准备一个方便打印二进制的工具函数，或者直接用调试器的二进制视图。Python里一行bin(x)就能做到，C语言里可以写一个通用的打印函数：

void print_binary(unsigned int x) { for (int i = 31; i >= 0; i--) { putchar((x >> i) & 1 ? '1' : '0'); if (i % 4 == 0) putchar(' '); } putchar('\n'); }

调试时，把每一步参与运算的原始值和掩码都打出来，然后对照纸面推导。我自己的习惯是，在写较复杂的状态转移前，先在草稿纸上画一个4位或8位的二进制示意，把x、x-1、-x、~x都列一遍，再动笔写代码。这个方法帮我避开过很多低级错误。

7.5 一套覆盖边界值的测试模板

位运算函数最怕边界值爆冷门。我常用的测试集是：0、1、-1、INT_MAX、INT_MIN、0x55555555、0xAAAAAAAA，再加几个常见的对齐数如64、255、256。测的时候重点关注三件事：符号扩展是否正确、位移后是否溢出、掩码是否把高位限制住了。很多看似正确的写法一测INT_MIN就会露馅，比如绝对值、右移、lowbit在边界值上很容易出问题。把这些用例固化下来，每次写完位运算函数直接跑一遍，能省很多事。

最后说一个我自己的习惯。凡是遇到“集合”“状态”“开关”“标志位”这类概念，我第一反应都是问自己：能不能用一个整数来表示？如果你的答案是能，那么后面不管是性能优化还是代码简洁度，都会上一个台阶。位运算不是玄学，它只是换了一种更接近硬件本质的视角去描述问题。希望这30个例子能帮你建立起这个视角，少踩我当年踩过的坑。