前两天在改一段状态枚举的性能瓶颈代码朋友问我为什么他写的判重逻辑比我慢好几个量级。我扫了一眼发现他用了一个数组去存所有已访问的组合每次查找都要线性扫描。我跟他说把一个集合压进一个整数里一行位运算就能判定包含关系。他把那段改成位掩码之后整个程序从秒级掉到毫秒级。位运算这个东西看起来只是 | ^ ~ 六个运算符但真正用熟了以后你会发现它能干的事远超“快一点点”这个层面状态压缩、集合运算、权限控制、协议解析、哈希混合、算法剪枝背后全都能用位运算一把梭。这篇文章整理了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 六个常用运算符一张表看清行为运算符含义典型场景易错点按位与提取位、清零位、判断包含优先级低于|按位或置位、合并字段不要和逻辑或||混用^按位异或翻转位、去重、无损交换很多人不理解自反性~按位取反生成掩码、补集Python中需注意无限位左移乘2、构造位溢出行为因语言而异右移除2、提取高位有符号数是算术右移异或是这里面最特殊的一个它的三个性质一定要刻在脑子里a ^ 0 aa ^ 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*i63位的标记。unsigned long bits[N / 64 1]; // 设置第x位 bits[x 6] | 1UL (x 63); // 查询第x位 if (bits[x 6] (1UL (x 63))) { /* 存在 */ }x 6相当于x / 64x 63相当于x % 64这里用位运算纯粹是为了效率。这是布隆过滤器、爬虫去重、海量数据排序等场景的基石。如果你用的是Pythonint天然就是无限长的bit数组直接通过|和操作即可调试起来非常方便。2.5 技巧5状态DP中的位压缩状态压缩动态规划可能是位运算在算法竞赛里最重要的应用。经典例子是旅行商问题dp[mask][i]表示已经访问过mask中的城市、当前位于城市i的最短路径。这里的mask就是一个整数比如0b10101表示城市0、2、4已经被访问。状态转移时尝试从城市i走到还没有访问过的城市jif (!(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的二进制没有10 -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_popcountJava用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是负数比如-5mask 0xFFFFFFFFx 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 技巧13lowbit提取最低位的1x -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 0b10101111x 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有标准库bitsetPython可以直接用整数配合、|操作代码既短又容易验证。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 技巧18BFS/DFS状态访问标记有些搜索题状态不是单纯的坐标而是“哪些物品已经取走”“哪些灯已经打开”“哪些格子已经变色”这类组合。这时候二维bool数组就不好使了因为状态空间是组合爆炸级的。解决办法是把整个状态编码成一个整数丢进visited集合里。比如某个谜题有20个开关每个开关的状态是0或1可以把所有开关状态拼成一个20位整数。每次操作翻转某个开关时state ^ (1 k); // 翻转第k个开关 if (!visited.count(state)) { visited.insert(state); }位运算在这里的作用不只是提速而是让“状态的生成和比较”变得直接、无歧义。用数组去表示一个复杂状态还要考虑哈希函数怎么设计用一个整数哈希就是它本身。4.5 技巧19N皇后位运算剪枝的进一步分析很多人第一次接触位运算剪枝时会被(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个例子能帮你建立起这个视角少踩我当年踩过的坑。