1. 位运算到底好在哪为什么大厂面试都爱考它先说个真实的经历。我当年刷题的时候遇到一道很普通的题判断一个整数是不是2的幂。大部分人第一反应是写个循环除2取余一路除下去。这种解法两分钟就写完了逻辑也清晰。但当我看到题解区有人写一行n 0 (n (n - 1)) 0的时候说实话那一瞬间我是懵的。我不知道这个式子为什么能判断2的幂也不知道位运算为什么可以把一段循环压缩成一行。后来我花了大概两天时间把位运算从基础到进阶彻底过了一遍——从与、或、非、异或开始到左移右移再到n (n-1)、x -x这类经典技巧最后到状态压缩和布隆过滤器这种系统级应用。学完之后回头看那些没学位运算时候写的代码好多地方都在用笨办法。位运算之所以是算法学习和面试中的常客我觉得核心原因有三个快、省、简。快是因为位运算直接作用于二进制位是CPU最底层的操作一条指令就能完成比加减乘除这类算术运算还要快。省是指很多场景下位运算能把几个布尔状态压缩成一个整数的几个bit内存开销直接降一个量级。简是指像上面那个判断2的幂的题一行位运算顶得上一整个循环代码可读性反而更高——前提是你看得懂。这篇文章不打算像教科书那样把真值表背一遍就完事。我尽量用这个技巧解决什么痛点——为什么它能成立——实际代码怎么写——在哪些题和系统里会用到这样的脉络去讲。希望能让没接触过位运算的读者一次性把这块地基打牢也让已经会用的读者再校准一遍自己的理解。2. 基础操作与直觉理解先搞清楚、|、^、~、、到底在干什么2.1 按位与只有两个都是1结果才是1位运算的所有操作都是针对二进制位逐个进行的。按位与的规则最简单两个位都是1时结果位才是1否则是0。用生活化的类比来理解假设你有两个开关电灯的电路是串联的只有当两个开关同时合上灯才会亮。1 1 11 0 00 0 0。这个操作最常见的用途就是筛选——你想保留二进制里的哪些位就把对应的位设为1去和其他数做与操作。判断一个数是奇数还是偶数所有人都知道用n % 2但在性能敏感的代码里更常见的写法是n 1。因为一个数二进制的最低位如果是1那它一定是奇数。整数在计算机里就是二进制数% 2等价于检查最低位是不是0。n 1得到1就是奇数得到0就是偶数。我刚开始学的时候犯过一个错误就是分不清和。在C语言和Java里是逻辑与有短路行为——左边为false右边就不执行了结果只有true和false。是按位与逐位计算结果是整数。这两个东西搞混调试起来非常痛苦。下面给一个小表方便对比记忆操作运算规则典型用途生活类比a b两个位都是1才为1取位、清零、判断奇偶串联开关a | b至少一个是1就为1置位、合并标志并联开关a ^ b两个位不同才为1翻转、去重、交换跷跷板~a0变11变0取反、配合与操作清位按灯的开关a n所有位左移低位补0乘以2的n次方往左挪箱子a n所有位右移符号位处理看类型除以2的n次方、取高位往右挪箱子2.2 按位或|有一个是1结果就是1按位或的规则恰好和与相反两个位只要有一个是1结果位就是1只有两个都是0时才为0。继续用开关类比这就相当于并联——任何一个开关合上灯都会亮。按位或在工程里最经典的使用场景是权限系统和状态标志。比如你定义四个权限读权限是1 0二进制001写权限是1 1二进制010执行权限是1 2二进制100删除权限是1 3二进制1000。要给一个用户同时赋予读和写权限不需要单独保存两个字段直接做PERM_READ | PERM_WRITE得到二进制011也就是十进制的3。一个整数就搞定查权限时再做按位与判断。搞底层网络编程的人对这个更熟。TCP报文头里的标志位——URG、ACK、PSH、RST、SYN、FIN——各占一个bit解析包头时就是靠按位与来检测某个flag是否被设置。比如检测SYN标志就是tcp_flags SYN_FLAG。用位运算而不是逐个字节比较是因为网络包解析要做的是高速数据面处理性能就是生命线。2.3 按位异或^不同为1相同为0按位异或是我个人认为位运算里最优雅的一个操作。它的规则是两个位不同结果位为1两个位相同结果位为0。这个操作有几个特别重要的性质值得单独记下来任何数异或自己结果是0x ^ x 0任何数异或0结果是它自己x ^ 0 x异或满足交换律和结合律a ^ b ^ c a ^ c ^ b同一个数异或两次相当于没有操作x ^ y ^ y x三条性质合在一起衍生出了一个非常著名的算法题一个数组里只有一个数出现一次其他数都出现两次找出那个数。最简单优雅的解法就是遍历数组做累次异或出现两次的数全部互相抵消变成0最后剩下的那个就是只出现一次的数。我第一次看到这个解法时有种这也能行的感觉仔细想想又觉得理所当然。它的本质是用异或模拟成对抵消的机制不需要额外开哈希表空间复杂度从O(n)降到了O(1)。还有一个我很喜欢的小技巧不借助第三个变量交换两个整数。经典写法是a a ^ bb a ^ ba a ^ b走一遍就明白执行完第一步后a变成了原始的a异或b第二步b变成了(a ^ b) ^ b等于a第三步a变成了(a ^ b) ^ a等于b。这个技巧在现代编译器里已经不太有实际性能意义了但非常能帮助理解异或的对称性质面试讲出来也显得有底蕴。2.4 按位取反~0变成11变成0按位取反就是把二进制位全部翻转0变11变0。在大多数语言里对有符号整数取反时要注意符号位也跟着翻转了所以~5的结果不是简单地等于-5附近而是-(51) -6。按位取反最常见的搭配是和按位与一起做位清零。比如你想把一个整数的低四位全部清零其他位保持不变x ~0xF。这里的0xF是低四位全是1的数取反之后低四位全0高位全1与操作就能把低四位砍掉。这个操作看起来简单但常在复杂的位操作表达式里出现稍不注意就会因为符号位的取反产生跟直觉相反的结果。我建议初学阶段先在纸上把二进制展开一位一位地走一遍别轻信脑子里的直觉。2.5 左移和右移、本质上是在快速乘除左移操作就是把二进制位整体往左移动n位右边空出来的位补0。一个整数左移一位相当于乘以2左移n位相当于乘以2的n次方。1 3就是二进制1000十进制的8。右移操作相对复杂一点。对于无符号整数右移时左边空出来的位补0这叫逻辑右移。对于有符号整数大多数语言里右移保留下来的最高位也就是符号位这叫算术右移。Java提供了两个不同的运算符是算术右移是逻辑右移。老牌的性能优化技巧是乘以2或除以2尽量写成 1或 1在某些老旧架构上运算速度有差异。但现代编译器早就自动做这种优化了我实际写代码时不会刻意追求这个。反过来我反而建议在工程代码里以可读性为主只有真正做到底层优化比如嵌入式、游戏引擎的关卡数据压缩、图形学的像素格式处理时才直接用移位操作。当然移位和算术不是完全等价的有个大坑当操作数的类型是带符号整数且做右移时负数右移并不是简单地除以2再取整的行为。比如在C语言里-3 1的行为依赖于实现有些情况结果是-2有些是-1跨平台时很容易出问题。能用除法的地方为了可读性别硬套移位。我自己在做状态压缩DP时最常用到左移用一个整数的第i位表示某个状态是否存在标记状态 i 时就是state | (1 i)检查状态 i 是否存在就是(state i) 1。这一套组合拳下来能把一系列布尔状态压到一个int里后面会细讲。3. 位运算里的高频经典技巧n (n-1)、x -x、lowbit 这些写法到底在干吗3.1 n (n-1)把最低位的1变成0这个可能是面试里出现频率最高的位运算技巧。一句话总结n (n-1)的结果相当于把n二进制表示中最右边那个1抹掉其他位保持不变。为什么看数学推导n减去1后从最低位的那个1开始到最低位为止所有位都发生了翻转。例如n 12二进制是1100n - 1 11二进制是1011。仔细对比1100和1011只有从第二位的1开始翻转了从这往高位的部分不变。再做按位与高位部分两个数相同保持不变低位部分一个是0一个是1全部变成0。所以低位那个1被抹掉了。这个技巧直接衍生出三个经典问题第一个统计一个整数二进制中1的个数。循环做n n (n - 1)每做一次抹掉一个1数一下循环次数就行了。LeetCode题号191属于必刷的基础题。我当年第一次写这个解法的时候试着用笔在纸上跑n 7111抹到000足足做了三次就能直观感受到循环次数跟1的个数严格一致。第二个判断一个整数是不是2的幂。2的幂的二进制特征就是只有一个位是1其余全是0。n (n-1)如果结果是0说明抹掉唯一那个1之后就是0了那它一定是2的幂。第三个枚举所有子集。如果集合里元素个数为n可以用一个整数mask表示某个子集其中第i位是1表示选中了第i个元素。要遍历某个mask的所有子集有一个经典循环for sub mask; sub; sub (sub - 1) mask。这个循环每一步都会拿到一个子集效率非常高。(sub - 1) mask的核心操作同样依赖低位1抹除的思想只是多了个mask钳制不要越过边界。3.2 x -x获取最低位的1所在的位置x -x在竞赛圈内被叫做 lowbit意思是拿到x二进制里最低位的那个1。比如x是12二进制1100-x在补码表示中是~x 1和x按位与之后会得到二进制的100也就是4。这就是12的最低位的1对应的数值。lowbit怎么用最有名的场景是树状数组。树状数组Fenwick Tree的update和query操作里都依赖i i -i和i - i -i来在索引树上跳转。有了lowbit树状数组才能在O(log n)时间内做前缀和更新和查询。我第一次接触树状数组时觉得这个跳转真是神来之笔但其实背后的数学原理就是补码结构。另一个场景和3.1结合可以快速把一个整数拆成若干个二进制位为1的位置然后配合哈希表做状态压缩的DP。比如你有一个集合每个元素有选中和未选中两种状态用mask表示想枚举mask里所有的元素编号代码可以这样写int tmp mask; while (tmp) { int lowbit tmp -tmp; int index __builtin_ctz(lowbit); // 计算lowbit末尾有几个0 // 对第index个元素做处理 tmp - lowbit; }这个模式在写状态压缩DP的时候非常常用。3.3 异或的应用场景从零开始找缺失值前面第2.3节已经讲过数组里找一个唯一不重复元素的解法。这里再引申两个变体第一个变体找缺失的那个数。给定一个包含0到n中n个数的数组找出那个没出现的数。解法是初始化ans n然后遍历数组让ans ^ i ^ nums[i]。因为0到n每个数理论上应该出现一次异或运算会把成对出现的全部抵消最后剩下的是缺失的那个。第二个变体找出数组中出现奇数次的元素。如果题目改成只有一个数出现奇数次其他数出现偶数次解法一样是全员异或。奇数次的数无法被抵消最终被留下来。这两个问题的共同点是通过异或的自反性把成对出现的信息抹掉。要理解这类解法不用死记结论记住x ^ x 0和x ^ 0 x就已经足够推导了。3.4 小心位运算符与逻辑运算符混淆的坑这部分很重要因为我自己在初学时为此踩过不少时间的坑。在C语言和Java这类语言里位运算符和逻辑运算符的符号非常接近但行为完全不同。语言位运算符逻辑运算符结果类型什么时候用C/C、|、^、~、、、||、!逻辑运算符结果是bool判断条件时Java、|、^、~、、、、||、!位运算符结果是int位操作时Python、|、^、~、、and、or、not位运算符结果是int位操作时比如在写if (x 1 0)判断偶数时如果x是负数呢-3 1的结果是1所以用位运算判断偶数是安全的但-3 % 2在C语言里是-1和0比较为false导致误判。正确处理方式是x % 2 0或者直接(x 1) 0不要写x % 2 ! 1。还有一个特别容易踩的Python坑Python里没有无符号整数概念负数左移和右移的行为跟C语言不太一样。在Python交互式环境里跑-1 1得到的是-1因为Python采用算术右移补齐符号位。如果你期望的是逻辑右移就得自己处理。老实说我在写Python算法题时如果需要逻辑右移一般就直接用(x % (1 32)) 1这样的手法来模拟32位无符号右移或者绕开负数场景。3.5 用二进制位拆分理解位掩码如果你能把上面几个技巧吃透就知道它们看起来眼花缭乱本质都是围绕某一位是0还是1做文章。位掩码的核心模型就是一套积木一个整数是一排开关盒第i位就是第i个开关开为1关为0。开就是置位state | (1 i)关就是清位state ~(1 i)查就是读位(state i) 1翻转就是异或state ^ (1 i)。在这个模型下不管你是处理权限、标志位、状态还是集合子集思路都是统一的。我在写算法题时看到集合很小元素数量不超过20布尔状态不超过30种这类条件第一反应就是能不能用状态压缩来表达。位运算和状态压缩是黄金搭档下面一节专门展开。4. 状态压缩与位掩码实战怎么用几个比特搞定原本要开一个数组的问题4.1 状态压缩DP解决旅行商问题的思路拆解先声明我不会在这一节把完整的TSP实现写完那样太长。我想展示的是位掩码如何把我去过哪些城市这个状态浓缩成一个整数。假设有n个城市从0到n-1编号你从城市0出发每个城市只能去一次问回到城市0的最短路径。这是经典的旅行商问题朴素穷举排列数是n!n稍微一大就爆炸。用状态压缩DP状态可以定义成dp[mask][i]mask表示已经访问过的城市集合i表示当前停留在城市i。mask是一个n位的二进制数第k位是1表示城市k已经访问过。状态转移时需要枚举下一个能去的城市j如果mask里还没有j那么能从dp[mask][i]转移到dp[mask | (1 j)][j]代价加上dist[i][j]。这个DP的复杂度是O(2^n * n^2)n20时大概十亿量级依旧是高复杂度但相比n!已经是指数级别里的优等生了。写代码时需要的位操作其实只有两类判断j是否在mask里(mask j) 1为0表示不在把j加入maskmask | (1 j)我在刚开始接触这个DP的时候特别不适应总想用数组记录访问历史。后来想明白了mask本身就是访问历史不需要额外数组。状态压缩的核心就是用bit的0/1映射元素的存在或缺失空间从可能的大数组压缩到单整数同时让状态转移变成了整数运算。4.2 实际工程里弱状态压缩的常见案例枚举子集和组合不知道多少人跟我一样写程序时需要遍历一个集合的所有子集。如果集合大小是20子集总数是2^20约100万个用位枚举完全扛得住。枚举所有子集的经典写法是n 4 for mask in range(1 n): selected [] for i in range(n): if (mask i) 1: selected.append(i) # 处理选中的子集这个写法看起来是两层循环但外层循环和位运算合起来实际上是把递归枚举选或不选压扁了。好处是代码极简内存占用极低每个mask就是一个子集的唯一标识。很多DFS的排列组合题——比如找到一组数字中和为target的组合——都可以改成这种迭代式枚举速度和可读性都有优势。需要注意当n超过25到30这个枚举在单机单线程下开始吃力。因为2^30已经超过10亿。如果集合真的达到这么大就要考虑折半搜索meet in the middle——把集合分成前后两半分别枚举子集再合并结果。这是我建议在面试中除了基本枚举外能额外展示的进阶技巧。4.3 哈希表里的布隆过滤器——位数组的经典工程应用布隆过滤器是数据结构课里经常被提到的概率型数据结构底层就是位数组和一堆哈希函数。它的核心操作是把元素通过多个哈希函数映射到位数组的多个位置插入时把那几个位置全部置1查询时检查这几个位置是否全部为1。只要有一个位置是0元素一定不存在全部为1只能说可能存在。工程实现里这个位数组常用byte数组模拟位级存储。假设位数组bitArray的长度是m位用byte数组实现时长度是(m 7) / 8。写bit的时候需要定位byteIndex bitIndex / 8bitOffset bitIndex % 8然后做bits[byteIndex] | 1 bitOffset。读bit的时候做(bits[byteIndex] bitOffset) 1。这个模式几乎跟我前面讲的mask完全一致只是粒度是字节内的位。所以不要觉得状态压缩只存在于算法题里像布隆过滤器、位图索引bitmap index、LSM-Tree里的布隆过滤器层都是位运算的工业级应用。我印象很深的是在一些分布式存储系统里为了减少不必要的数据读取每个数据块都会配一个布隆过滤器查询前先用它过滤掉肯定不存在的键。这里面位运算的性能直接决定了过滤的速度不能出任何误差。4.4 哈希函数的雪崩效应与散列优化的位运算细节还有一个容易被忽略的场景是哈希表的内部实现要均匀散列。比如Java的HashMap里哈希值hashCode()与hashCode() 16做异或——所谓的高低位混合——目的是让高16位的信息也参与低16位的计算提高散列均匀度。这种写法就是典型的互补型位运算优化。很多Seed型哈希算法、校验算法里也有大量位旋转rotate和移位操作。比如CRC32、MurmurHash左移右移异或按位与全都有是位运算的高密度表演区。读这类代码时如果对位运算没有感觉基本跟看天书一样。而理解了位运算之后会发现这些算法的设计逻辑是最大化雪崩效应让输入的微小变化扩散到输出的所有位。有些面试题会问为什么HashMap要用(n - 1) hash而不是hash % n来定位下标这背后也是位运算。当n是2的幂时hash (n - 1)和hash % n是等价的但前者更快。Java的HashMap在resize时桶数始终是2的幂正是为了能用这个位运算代替取模。4.5 工程实战权限系统的位掩码设计与实现这是我个人项目里用过很多次的一个设计。假设要实现一个文件权限系统有四种权限读、写、执行、删除。定义常量PERM_READ 1 0 # 4 PERM_WRITE 1 1 # 2 PERM_EXEC 1 2 # 1 PERM_DELETE 1 3 # 8赋予用户读写权限时perms PERM_READ | PERM_WRITE # 得到数值3检查用户是否有写权限时if perms PERM_WRITE: # 有写权限撤销写权限时perms ~PERM_WRITE这套拿bit做标志位的玩法在Linux的权限系统里有直接呈现——rwx三个位。一个chmod命令的数字本质上就是三个bit的整数。真的成功把设计从两组布尔属性升级为一个整数之后你会发现所有权限判断都变成了单条位运算指令而且方便持久化存储、网络传输和比较。我还没见人用这个权限系统踩过大坑但初学者常常会犯一个小错误常量本身是从0开始的如果PERM_READ 1 0得到1、PERM_WRITE 1 1得到2看起来像是2和1但千万别跟十进制的大小混在一起。检查权限时只能做与运算不能直接比较数值相等否则会被组合权限弄错。比如一个用户拥有读和执行权限perms是5而这个5既不等于1也不等于4但perms PERM_READ和perms PERM_EXEC都为真。5. 进阶技巧与易错细节右移、溢出、符号位、无符号整型5.1 算术右移和逻辑右移的区别为什么会搞出bug右移分为算术右移和逻辑右移这点前面简单提过这里展开说明。算术右移保符号最高位是1就往左补1最高位是0就往左补0这样负数右移后仍然是负数。逻辑右移高位一律补0不关心符号结果是非负整数。用Java来演示区别最直观int a -8; // 二进制补码 11111111 11111111 11111111 11111000 int x a 1; // 算术右移结果 -4 int y a 1; // 逻辑右移结果 2147483644同样是移动一位二进制和的结果天差地别。如果代码里对无符号语义的整数用了算术右移就会在数值计算时犯下难以察觉的灾难性错误。C语言里没有运算符对无符号整型做右移默认是逻辑右移。对有符号整型做右移标准没有完全确定但主流编译器都按算术右移处理跨平台时要谨慎。如果你正在做网络协议解析塞进代码里的都是无符号字节序列记得统一用无符号整型别混用。5.2 左移的溢出和符号位翻转左移操作在数学上是乘以2的幂但受限于整型的位宽高位移出去的直接丢弃。比如32位int1 31得到的是二进制最高位为1的数按有符号解读就是负的-2147483648这经常会让初学者以为计算错了。请注意这个溢出并不是语言错误而是整数位宽决定了它只能存那么多位。在操作位掩码时如果元素编号从0到n-1想用1 i时要注意i的范围。在32位int里最大用到位30正数范围位31是符号位位再往上全部溢出。所以当状态压缩的元素数量超过30时就要换64位整型了。我做过一个组合枚举的题集合大小是35一开始用Python的int直接1 35没问题因为Python的整数是任意精度但换到C或Java时35位的mask塞不进int或long的常规表示里。这时候要么改用数组或别的结构要么换成long long在C64位Java用long。5.3 负数取模和位运算的交互我前面提过n % 2判断奇偶在负数时容易出错原因值得展开。在C里-3 % 2的结果是-1而(-3 1)的结果是1。如果你写if (n % 2 1)判断一个整数是奇数对负数来说永远是false。这显然是错的。标准做法是if (n 1)来判断最低位是不是1这是最安全且最快的。如果非要判断偶数就是if (!(n 1))。这个坑别看小在实际工程中引起过很多次隐蔽的bug属于常见面试题说说 % 和 的区别的变体。在底层场景比如图像处理和网络协议里操作的数据经常是字节流、状态码尤其要注意负数和无符号类型的交互。很多老练的工程师都有个习惯位运算尽量用无符号类型做省得补码符号位参与计算造成困扰。5.4 位运算在性能敏感场景里的实际收益讲实用点位运算现在不是万能钥匙。在现代CPU上整数除法相对慢但整数加减乘都很快。编译器对乘2、除2的都会自动优化成移位。所以我写代码的原则是不为了用位运算而用位运算更多考虑的是内存压缩和代码表达力。有一类场景位运算收益很明显大规模位图。比如一个系统需要记录上亿个用户是否在线用boolean数组存一个用户要1个字节如果用bit存一个用户只要1个bit内存直接降到1/8。对这种海量数据内存的节省是实质性的这时位运算不只是一个优化技巧而是存亡级别的架构决策。另外一类场景是硬件寄存器读写。嵌入式开发中配置寄存器往往就是往特定bit写0/1。此时位运算是唯一正确的写法没有替代方案。我在嵌入式项目里看到工程师用REG | (1 3)开启某个硬件功能用REG ~(1 3)关闭某个功能非常干脆。5.5 Python里的位运算细节无限位宽和负数处理Python的整数是任意精度的这让位运算的行为和C系语言不同。最典型的就是没有固定的位宽所以~x的结果不是变成另一个有限位宽的补码形式而是得到一个看起来奇怪的负数。比如在C里~5得到-6在Python里~5也是-6但如果你拿Python的x 0xFFFFFFFF去试图模拟32位截断就会涉及到无符号化和有符号化的转换问题。我在LeetCode刷题时经常看见Python题解里写n 0xFFFFFFFF来模拟无符号32位这个技巧广泛存在但实际使用时要明白它只是低32位保持不变数值语义已经从有符号变成无符号大数了后续再和负数比较时要小心。Python里还有个坑如果代码里用位运算模拟C语言的溢出比如a 25后丢弃高位Python不会自动截断。你需要显式做result ((1 32) - 1)来模拟32位截断。我写过几次跨语言的算法移植每次遇到这种隐式截断的差异都很头疼。做位运算跨语言移植时建议先划定统一的整型位宽语义然后每个位操作函数都包一层mask否则很难调试。6. 位运算在各类经典算法题里的高频应用盘点6.1 常考题模板统计1的个数与判断2的幂这两个模板在面试中出现频率极高正好也是位运算入门的首选。我整理一下可以直接抄的代码统计二进制中1的个数int popcount(int x) { int count 0; while (x) { x (x - 1); count; } return count; }每执行一次x (x - 1)x就少了一个1。循环次数严格等于二进制1的个数时间复杂度O(k)k为1的个数。如果是系统库C可以直接用__builtin_popcountJava用Integer.bitCountPython用x.bit_count()。能用库函数时我不建议手写但面试里如果考察原理还是把原理写明白更好。判断2的幂bool isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }这个写法的精妙之处在于利用2的幂二进制只有一个1的特性一行代码同时完成了三个检查n大于0二进制只有一个1没有其他位。6.2 只用一行异或解决的唯一不重复系列前面讲过的找出只出现一次的数字系列整理成表问题输入特点解法复杂度一个数出现一次其他出现两次整型数组全员异或O(n)时间O(1)空间一个数出现一次其他出现三次整型数组逐位统计每一位出现次数不能整除3的就是答案对应的位O(32n)时间O(1)空间两个数出现一次其他出现两次整型数组全员异或得到a^b再按最低不同位分组异或O(n)时间O(1)空间第三个问题很有意思。全员异或得到的是a ^ b因为其他成对的都抵消了。a和b不同所以a^b的二进制里至少有某一位是1。找到这一位最低位的1用x -x找然后按照这一位是0还是1把整个数组分成两组每组再各自异或就能分别得到a和b。这类题目的共同灵魂是异或能抹掉成对信息。想通了这一层再遇到什么落单的数丢失的数重复的数都不会慌。6.3 结合位运算的排序与查找优化排序算法里归并排序和堆排序是主流位运算也会出现在一些排序技巧中。比如基数排序Radix Sort在某些实现里会按二进制位分组本质就是对每一个bit做桶分这正是位运算发挥的地方。虽然日常写业务代码几乎不会手撸基数排序但想明白把位拆开逐bit分组这个思路对理解位运算很有帮助。查找方面二分查找里有一句经典写法int mid (low high) 1;这是为了防止lowhigh溢出还把符号位弄坏才用的无符号右移。很多人写int mid (low high) / 2;在极端情况下可能溢出为负数一旦low和high很大时就会出bug。用位运算的写法(low high) 1当然也可以但要保证没有溢出风险Java源码里用 1等于把无符号右移变成了防溢出的必然之选。再比如堆排序和树状数组里lowbit的索引变化本质就是位运算驱动的跳转。树状数组之所以在竞赛里长盛不衰正是因为它用lowbit把前缀和查询变成了O(log n)的BIT节点跳转代码又短又快。6.4 位掩码在回溯算法里的剪枝效果回溯算法是暴力搜索的通用框架但剪枝效率往往决定能不能跑完。常见的NP类题目比如八皇后数独子集生成都可以用位掩码来优化判断。八皇后问题里可以用三整数分别表示列、主对角线、副对角线的占用状态。每一行尝试放皇后时可用的列位置 ~(col | dia1 | dia2)与上一个全1掩码做与得到当前行可以放的列的位集合。然后通过x (-x)依次取出最低位的可用位置尝试。这个题用位运算实现代码量比用布尔数组少了至少一半速度也更快。很多竞赛选手偏爱位运算剪枝因为可以不用递归传数组只用三个整数的拷贝就能在分支搜索里轻量传递状态。这类技巧学起来有点门槛但如果能掌握把决策集编码为位掩码回溯代码的整体结构会清晰很多。7. 踩坑记录与调试建议位运算代码出了错怎么快速定位7.1 符号位和类型转换引发的错误最典型的错误是类型转换。在Java里一个byte8位有符号和int做位运算byte会自动提升为int此时byte的符号位会扩展到整个int的高位。比如byte b (byte) 0xFF;内存里是11111111提升成int后变成0xFFFFFFFF你再b 0xFF得到255但如果直接b参与运算就可能出问题。解决方式是在操作前显式把byte转换到无符号语义比如int unsignedByte b 0xFF;。我在做二进制文件解析时写过不少这种代码必须每一步都清楚当前变量在内存中的位型。7.2 移位位数超过类型位宽在C/C中如果移位的位数等于或超过左操作数的位宽行为是未定义的。比如32位int执行a 32在C里是未定义行为你不知道会得到什么。Java里对int移位会移位右侧操作数对32取模a 32等于a 0即a本身对long移位则对64取模。不同语言处理完全不一样这也是写位运算时容易踩的可怕陷阱。建议凡是要移位的量手动确保在0到位宽-1之间。如果需要用到更大的移位就先把类型转成更宽的整型再做。7.3 调试位运算的三个有效手段我调试位运算时最常用的三招打印二进制、用二进制小集合验证、拆分成单步表达式。第一招是打印二进制。写一个函数把整数转成二进制字符串比如在Python里用bin(x)C里可以自己写个循环把每一位抠出来。看到打印的位串很多问题立刻就清晰了。第二招是抓一个小集合验证。比如写状态压缩DP时不要一开始就跑n20先用n3或n4然后用枚举法暴力算一遍结果和位运算版本对比。我记得自己调TSP的DP时就是n4反复跑。小集合测试不是浪费时间它可以快速暴露在位掩码和状态转移里的逻辑错误。第三招是把复杂表达式拆开。不要写a | b ~c d这种没人能一秒读懂的复合表达式。拆成多步每步单独打印中间结果。uint32_t a 0x0F0F; uint32_t b 0x3333; uint32_t c ~b; uint32_t d (c 0xFF) 4; uint32_t result a | d;这样一旦结果不对你很快能定位是哪一步的位算错了。7.4 位运算的优先级写代码前先标好括号C系语言的位运算符优先级是个经典的坑。的优先级低于所以if (a b c)会被解析成if (a (b c))完全不是你想要的。真心建议位运算和别的操作混在一起时一律加括号可读性会好很多。尤其在后端工程里那些权限检查写成一个复杂布尔表达式时不加括号别人包括三个月后的你根本没法维护。我在自己的代码风格里有一条铁律位运算表达式必须实时加括号绝不裸奔。7.5 用单元测试保护位运算代码位运算代码很难从肉眼看测试出来所以我一直建议给位操作函数写单元测试。一个n位整数穷举它的所有值来测试某个位运算是否满足预期。像判断奇数这种直接把正整数范围从0到1000全部跑一遍和% 2的写法对比。像lowbit这种可以设计一个小集合逐个确认输出值。我在做数据结构的底层函数时也习惯写一批随机黑盒测试生成随机数用暴力方法算一遍期望结果再和位运算结果对比。别嫌麻烦位运算的bug一旦流入上层排查成本会以指数级上升。8. 我能给到你的实操学习路线和经验心得如果你是完全的新手我的建议是别贪多。按下面的顺序来先把六个基础运算符、|、^、~、、的真值表背熟并且能在纸上手动算一个8位二进制数的各种运算。掌握三个核心模型状态掩码某一位是0还是1、低位操作n (n-1)、lowbitx -x。刷十道位运算入门题比如位1的个数、2的幂、只出现一次的数字、反转二进制位、交换数字、汉明距离。尝试一到两道状态压缩DP接受它需要时间理解这个事实。我用了一周才从完全懵到能用mask写状态转移。在工程里主动找一个可用位掩码的场景重构一下比如权限系统验证一下自己到底有没有掌握。我个人在实际操作中的一个体会是位运算的难点不在运算符本身而在于脑海中构建二进制位图的能力。你看到n (n-1)时应该能在脑子里看到一个二进制数它的最后一个1正在消失。这种图像化思维需要大量练习才能建立没有捷径。另一个体会刷题时遇到一道位运算题试着用位操作和常规操作各写一遍对比两者的代码量和性能。很多题目你刚开始会觉得位运算写法像魔法等你写了几十遍它就变成了直觉。最后分享一个小技巧给要面试的朋友面试时如果用了位运算优化别只写代码把这个写法为什么能成立从位层面解释一遍。面试官通常不仅考察你会不会用还考察你是否真的理解。能清楚地讲出来表达的是你对计算机底层运作方式有精准把握这在算法面试里是很加分的信号。