1. 位运算到底是什么先建立二进制直觉如果你刷算法题早晚会遇到这样一道题一个整数数组里除了某个元素只出现一次之外其余每个元素都恰好出现两次找出那个只出现一次的元素。第一次见这题的人十有八九会先想到哈希表计数再想到排序后扫描前者要额外开空间后者要破坏数组或者承受排序的时间成本。但懂位运算的人只需要一个异或循环几行代码就把空间复杂度压到O(1)。这就是位运算一直被认为“看着神秘、用着真香”的原因。位运算说到底就是对二进制位直接做逻辑操作。普通加减乘除处理的是整数作为一个整体的数值而位运算把整数拆成一个个独立的比特位每一位都可以看作是0或者1的一个开关状态。你把两个整数按位进行运算相当于把两组开关逐位比对输出一组新的开关状态。这个概念一旦建立起来后面所有的技巧都是水到渠成。要理解位运算还得先把整数在计算机里的存储方式搞清楚。现在几乎所有主流语言里的有符号整数都是按补码形式存储的。补码规则很简单正数的最高位是0后面直接存二进制值负数则是“按位取反再加一”最高位是1这个位用来表示符号。比如int占32位1就是 ...0001-1则是 ...1111。正因为补码的这个设计位运算才能同时兼顾正数和负数而不需要额外做特殊分支处理。这一点特别重要因为位运算里有一个新手最常踩的坑对一个数按位取反算出来的结果为什么会是负数原因就出在补码上。当你对5二进制0000...0101取反时得到的是1111...1010这在补码体系里就是-6。不是说“取反就是负的”而是取反后所有位翻转最高位也变成1了解释成有符号整数自然就是负数。所以后面讲~操作符时你会发现它的实际效果是“x取反等于-x-1”。位运算相比普通运算有几个底层优势第一它不产生进位也不会借位每一位都是独立的这样用起来非常直接第二它在大多数处理器上都有对应的一条机器指令执行速度极快第三它天然适合做状态压缩和多标志位管理。前两个优势决定了算法复杂度能降下来第三个优势让位运算在状态压缩DP、位图去重这类场景里大放异彩。2. 六大操作符逐一拆解每个都能立刻用上位运算一共就六个基础操作符按位与、按位或、按位异或、按位取反、左移、右移。每个操作符的性质和应用场景都不一样但都有一个共同点都是对二进制位逐位处理不涉及进位或借位。下面逐个说清楚。2.1 按位与只有两个都是1结果才是1按位与的规则一句话就能概括两个对应的二进制位都是1结果位才是1否则就是0。英文叫AND你可以理解成“两个开关串联必须同时闭合灯才亮”。这个操作符最常见的用途是“取位”和“清零”。比如判断一个整数是奇数还是偶数不用取模直接让它和1做按位与。因为二进制的最低位如果是1说明这个数是奇数如果最低位是0说明它是偶数。写成代码就是if (x 1)。为什么这样能判断因为任何整数都可以写成“若干2的幂相加”的形式除了最低位之外其它位代表的都是2的倍数只有最低位决定奇偶性。另一个高频用法是判断一个数是不是2的幂。2的幂在二进制里只含一个1比如8是100016是10000。如果一个数x是2的幂那么x-1的二进制就是它那个1右边的所有位都变成1比如16减1是15二进制01111。这时x (x-1)的结果一定是0。如果这个条件成立再加一个 x 0 的判断就能确定x是2的正幂次0要单独排除。这个公式我几乎可以算是背下来的太常用了。跟清零相关的用法也很多比如你想把一个数的低4位清零保留高位就用x 0xFFFFFFF0在十六进制里F代表四个10代表四个0。更直白一点直接把想要保留的位写成1想要清掉的位写成0这个掩码跟原数做按位与就行。这也是“位掩码”bitmask这个概念的最基本形式。2.2 按位或|与按位或赋值|有一个是1结果就是1按位或的规则是两个对应位只要有一个是1结果就是1。类比成电路就是“两个开关并联闭合任何一个灯都亮”。它最常见的用途是“置位”也就是把某一位从0变成1或者确保某一位是1。举个例子你要把某个整数的最低位置为1但同时不想改变其它位就可以直接x | 1。这里|就是“按位或赋值”的复合操作符等价于x x | 1。C语言、C、Java、Python、Go里都有这套复合赋值操作符除了|之外还有、^、、写法跟完全同一个套路。很多人刚接触时容易把|和记反其实你只要记住“或”是“放宽条件一个为1就通过”跟“与”正好相反。按位或在某些“多标志位”场景里特别有用。比如你设计一个配置项用8位表示8种开关0x01表示启用日志0x02表示启用缓存0x04表示启用压缩。想同时启用日志和缓存就config | 0x01 | 0x02。想检查日志是否开启就if (config 0x01)。这样用一个整数就能管理一组布尔标志比开八个布尔变量清爽得多这也是位运算在工程实践里很常见的用法。把32位整数的每一位当作一个独立的布尔开关这一整个整数其实就是一个“位数组”。在位图Bitmap结构里你甚至可以用一个很长的位数组来标记大量数据是否存在比如有10亿个URL需要做去重判断用哈希表会吃几GB内存但用位图一位只占一个比特10亿个位大约是125MB内存这个数量级上的差距就是位运算对空间效率的贡献。2.3 按位异或^相同为0、不同为1最值得玩的是它异或的规则是两个对应位相同结果为0不同结果为1。它相当于“二进制的不等于号”在逻辑电路里叫半加器的基础。为什么叫“半加器”因为1 ^ 1得到0正好是11的二进制结果去掉进位所以有人说异或是“不带进位的加法”。异或有三个性质做算法题时简直是万能钥匙。第一任何数和自己异或结果是0因为每一位都一样全是0。第二任何数和0异或结果还是它自己。第三异或满足交换律和结合律也就是一堆数异或在一起顺序怎么换都不影响结果。这三个性质放在一起产生了一个经典结论在一堆数字里如果某个数出现奇数次其他数都出现偶数次把所有数全部异或起来就能直接得到那个出现奇数次的数。原因是成对出现的数会两两抵消成0只剩下那个落单的。异或还有一个让初学者目瞪口呆的巧用不用临时变量交换两个整数。a ^ b; b ^ a; a ^ b;这三行跑完之后a和b的值就互换了。原理就是利用“异或自己等于0、异或0等于自己”这两条性质完成值的搬移。不过我得提醒一句这个技巧在实际生产代码里并不推荐可读性差而且在内置类型交换时只要用swap(a,b)一行就够了编译器还能自动优化。它更大的意义其实是帮人理解异或的性质面试时偶尔会作为小知识点聊两句。在加密领域里异或也有一席之地。一个明文和一个秘钥做异或得到密文密文再用同一个秘钥异或一次就还原成明文因为text ^ key ^ key中间那两项抵消了。很多早期的简单加密算法就是这么做的虽然现在没人拿它当主力加密方案但理解这种“对称加解密”的思想对学信息安全挺有帮助。2.4 按位取反~把所有位0变1、1变0结果常常出乎意料按位取反是最容易让人懵的操作符。它把每一位都翻转0变成11变成0。在补码体系下它的效果就是~x -x - 1。你可能会算出一些看起来很奇怪的数~5是-6~0是-1~(-1)是0。它最实用的场景之一是构造掩码。比如你想把一个整数的低n位都置为1可以这样写(1 n) - 1。如果你想保留高位部分、把低n位清零那就用取反操作x ~((1 n) - 1)。这里~((1 n) - 1)的意思就是“低n位全是0其余位全是1”跟x做按位与就能把低n位抹掉。类似这种“先生成一个全1掩码再取反”的模式在状态压缩DP里几乎天天用到。理解了取反的实际含义你也会明白为什么“清零”和“置位”经常要配合用。置位用|只需要把对应位掩码写成1清零用需要把对应位掩码写成0但通常不好直接写一大串0就往往会借助~把原来的“1掩码”取反得到“0掩码”。这是位运算里最常用的一套组合拳。2.5 左移和右移乘以2除以2的底层实现左移非常好理解把二进制位整体向左移动右边空缺的位补0。每左移一位数值就乘以2左移n位数值就乘以2^n。在不开优化的编译器里x 1和x * 2的结果一致但位运算指令在理论上更接近底层某些极端性能敏感的场景里确实有差别。右移则是把位向右移动每右移一位数值就除以2并向下取整。要注意右移分两种算术右移和逻辑右移。算术右移在左边补的是符号位负数右移左边补1逻辑右移在左边补0。C/C里对普通有符号整数执行 通常是算术右移Java里还额外提供了专门做逻辑右移初学Java的人经常在这里栽跟头。左移最常见的应用就是构造掩码和做状态压缩。比如枚举一个集合的所有子集时1 i表示只包含第i个元素的子集(1 n) - 1表示包含前n个元素的完整集合。快速幂算法里指数按二进制拆开底数不断自乘每一轮的结果对应指数的一位这本质就是左移配合乘法在做事的思路。右移在某些场景里比除法更符合需求。比如想把一个整数拆成逐位处理x 1配合x 1每次取最低位再右移一位就能从低到高遍历二进制位。这种逐位遍历在判断二进制回文、转换二进制字符串时很好使。如果你在高性能代码里做这种循环用右移显然比每次取模再除以10要快。有一点要注意位移的位数量不能超过类型的位宽否则在C/C里属于未定义行为。比如32位int写x 33的结果是完全不可预期的有的编译器会取模成移动1位有的干脆给出随机值。这种坑非常隐蔽线上代码一旦踩进去就特别难查我建议在写这种代码前先判断n是否在合法范围内。2.6 复合赋值操作符别记反了C系语言里,|,^,,这些复合赋值操作符都有对应的含义。x | y就是把x按位或上y之后重新赋给xx y同理。很多初学者第一次看到a (b | c)这种表达式会慌实际上你只要按“先算右边、再算左边、最后赋值”的顺序拆开读就没什么神秘的。写位运算代码时我个人的习惯是涉及到清除、置位这种“原地修改一个整数的某几位”的场景用复合赋值能让代码更紧凑但如果表达式本身已经很长或者后续要给其他人维护我会分开写成单独一行再加注释说明掩码的含义。位运算最大的优势是简洁最大的劣势也是简洁——过分的简洁就是可读性灾难这一点后面讲避坑时还会再提。3. 位运算核心技巧清单覆盖90%面试场景的套路操作符本身都是死的真正值钱的是那些组合玩法。我在下面的段落整理了一套高频技巧每个都有原理说明方便你不仅会抄还能在换题时判断该用哪个。3.1 奇偶判断、2的幂判断、大小写转换一行解法判断奇偶if (x 1)你几乎在任何编译器里都不会看错。但注意这个判断对负数同样成立因为补码表示下最低位仍然是1代表奇数、0代表偶数。判断2的幂x 0 (x (x - 1)) 0。这个公式在前面已经解释过了但我还想补充一句它的实际应用场景哈希表扩容时判断容量是不是2的幂、分页系统判断偏移量是否对齐、某些缓存策略里判断是不是一轮的整数倍都会用到这个判断。很多算法库在初始化时都会先做一次这个检查用来决定要不要调用对齐函数。大小写转换是另一个经典一行解。小写字母转大写ch 0xDF也就是把二进制第5位清零大写转小写ch | 0x20把第5位置1。如果你手头没有ASCII码表简单记一下大写和小写字母的ASCII码之间差32正好对应二进制的第5位。所以对英文字母做大小写转换本质就是翻转第5位。还有些更骚的写法是ch ^ 0x20可以在大写和小写之间来回切换这个在面试里属于锦上添花的小知识不一定值得在工程里用。3.2 无临时变量交换和绝对值计算异或与右移的组合交换两个数我在前面已经展示过三行异或版本。除了面试秀技巧之外它的核心价值其实是让你理解异或的可逆性。实际工程代码里还是老老实实swap(a, b)但如果你在做一些嵌入式开发寄存器数量极其有限的环境下这个技巧确实有出现过所以了解原理不算亏本。取绝对值的位运算写法是(n ^ (n 31)) - (n 31)。拆开看就两步先让n右移31位如果n是正数结果是0如果是负数结果是-1全1。然后n异或上这个值正数异或0不变负数异或-1等于把所有位取反此时得到-n-1。最后再减去n 31正数减0不变负数减(-1)等于加1刚好补回刚才多减的1得到绝对值。这套写法的数学基础就是补码和取反的关系能看懂以后你对负数在计算机里的存储就彻底通了。不过这种代码在生产环境里也不太推荐abs函数已经够快且有编译器优化这里同样是考研基础。3.3 x (x-1)清掉最右边的1统计二进制1的个数x (x - 1)的效果是“把x二进制里最右边那个1变成0”而其它位都不动。这个结论用10的二进制1010验证一下1010减1是1001与运算结果是1000最右边的1确实被清掉了。1000再减1是0111与运算结果是0两个1都被清掉了。有了这个工具统计一个数二进制里1的个数就很简单循环执行x (x-1)每执行一次就少一个1直到x变成0。循环次数就等于是1的个数。这个算法比“一位一位右移判断32次”的次数更少因为很多数二进制里1并不多。它还有一个变种应用判断一个数是否恰好有一个1那就是2的幂以及处理状态压缩DP里“去掉某一个元素”的操作——比如从集合mask中删掉第i个元素可以写mask ~(1 i)但如果明确知道第i位是1直接mask ^ (1 i)更简洁。现代CPU和主流编译器还提供硬件级的人口统计指令比如x86的POPCNT写C时可以用__builtin_popcount(x)写Python用int.bit_count()。这些函数的原理很多都是用这种逐位清除或查表法但最终执行速度会更快。理解x (x-1)仍然是基础因为面试场合写代码时不一定允许你调内置函数。3.4 lowbitx (-x)取得最低位的1树状数组的命根子x (-x)得出的结果是一个只保留x二进制中最低位的那个1的掩码。举几个例子lowbit(12)12的二进制是1100最低位的1在第三位也就是二进制0100即4lowbit(10)10的二进制1010最低位1是第二位的值2。为什么成立因为负数在补码表示下是“按位取反再加一”加一这个动作会使得原本最低位的1右边的所有0变成0最低位的1保持不变而它左边的所有位全被取反。这样一来x和-x做按位与只需看最低位的1。lowbit最出名的应用是树状数组Fenwick Tree。这个数据结构维护前缀和时每次更新和查询都要用到lowbit来确定下标要加减多少。比如更新一个位置之后下一个要被更新的下标就是i lowbit(i)查询前缀和时每次i - lowbit(i)。没有lowbit树状数组的代码根本没法写所以如果你要做进阶数据结构lowbit属于必须滚瓜烂熟的知识点。lowbit也可以用来快速统计1的个数循环x - lowbit(x)每减一次就少一个1直到x变成0。这和x (x-1)的效果一样只是思路不同。lowbit在状态压缩DP里也常常用来枚举当前集合中存在的元素或者判断某个位是否被选过。3.5 位掩码与子集枚举用整数代替布尔数组一个n个元素的集合它的任意子集都可以用一个n位的二进制数表示第i位为1表示包含第i个元素为0表示不包含。这个思路在算法竞赛里叫状态压缩使用频率高得惊人。枚举一个集合的所有子集最简单的方法就是遍历for (int mask 0; mask (1 n); mask)。这个循环覆盖了所有可能的组合每一次都可以根据mask的每一位来决定要取哪些元素。暴力枚举子集的时间复杂度是O(2^n)看起来好像很暴力但在n不超过20或者更小的时候这反而是最直接的暴力解法。很多人第一次写“枚举数组所有非空子集并求和”这种题时用回溯写一堆递归代码最后回头一看不如mask循环直接。子集枚举能做的题太多了给定一个数组找出所有和为目标值的子集找出最大子集使得没有两个元素相邻判断一个集合能否分成两个和相等的子集……这些题的暴力解法几乎都可以挂到mask枚举上。当你发现dfs回溯写起来很绕时先想想能不能用二进制mask表示搜索状态往往能把問題简化不少。位掩码还有一层好处状态本身是整数能直接用来做记忆化搜索或动态规划的键。比如状态压缩DP里经常写dp[mask]表示“当前状态是mask时的最优值”这种用整数做索引的DP数组天然比用字符串或数组做键快得多。这也是为什么很多“状压DP”题一上场就是位运算。3.6 快速幂、移位实现加减乘进一步理解二进制的数学意义快速幂是一个能体现位运算威力的经典技巧。比如计算a^b mod m朴素做法是连乘b次时间复杂度O(b)快速幂把b按二进制拆开比如b13二进制1101那么a^13可以写成 a^8 乘 a^4 乘 a^1。从最低位循环每轮让底数自乘一次a a * a % m同时把指数右移遇到当前位为1时把结果乘上当前底数。这样只需要循环约log2(b)次也就是O(log b)级别。这个算法里那行b 1和判断b 1就是位运算的直接应用。反过来用移位实现乘法和除法也是理解底层计算的好途径。x * 10可以写成(x 3) (x 1)就是8倍加2倍。x / 2可以写x 1但注意这是向下取整和真正的除法在负数时行为不完全一致所以工程代码里还是直接用除号。类似这种手工拆乘法更多是在你对性能敏感到极点、并且确定数据范围不会溢出的场景下才会用。还有一个小技巧是“二进制还原反转”。比如要把整数x的二进制位整体反转可以每一位取出来再放到对应位置。虽然这个操作本身不太常用但是那个“取最低位、原数右移、结果左移、放入”的循环写法会让你对移位操作形成肌肉记忆遇到其他需要从低到高扫描二进制位的题时能顺手写出。4. 算法实战从题目倒推位运算的价值这一节我挑几道特别有代表性的算法题从解题思路到实现细节完整过一遍。这些题在网上各种刷题平台都能找到原题或变体难度从入门到中等覆盖面刚好是把前面讲的操作符都调动起来。4.1 只出现一次的数字异或扫一遍题目一个整数数组里除了某个元素只出现一次之外其余每个元素都恰好出现两次找出那个只出现一次的元素。思路推荐用异或。初始化一个变量ans 0遍历数组不断做ans ^ num。根据异或的性质两个相同的数异或为0任何数和0异或不变所以所有成对的数字都会抵消干净剩下的就是落单的那个。这个解法为什么值得记因为它把额外空间降到O(1)时间复杂度也只有O(n)。如果用哈希表空间是O(n)如果先排序再扫描时间也要O(n log n)。在面试里你只要能说出异或解法再解释清楚三条性质基本就能证明你对位运算有深入理解。代码大致这样写int singleNumber(vectorint nums) { int ans 0; for (int num : nums) { ans ^ num; } return ans; }这个题还有个进阶版如果数组中除了一个元素出现一次其他元素都出现三次怎么办那就不能直接用异或了因为三个相同数异或不会消掉。但可以做“逐位统计”统计每一位上1出现的次数如果某一位上1的个数模3不为0说明那个只出现一次的数在这一位上是1。这也是位运算思想的高级应用本质上利用的是“按位独立”的性质。4.2 数组里有两个只出现一次的数字分组异或题目变体一个整数数组里有两个数字只出现一次其余数字都出现两次找出这两个数字。第一步还是把所有数异或一遍得到的结果是那两落单数字的异或值记为xor_sum。因为两个数字不同所以xor_sum的二进制里至少有一位是1。这一位表示在二进制这一位上两个落单数字一个是0、一个是1。第二步找到xor_sum中任意一个为1的位最方便的是用lowbit xor_sum (-xor_sum)提取最低位的1。第三步按这一位把数组分成两组这一位为1的一组这一位为0的一组。那两个落单数字必然被分到不同组而其余成对的数字在每一组里依然成对。分别对两组做异或就会各自得到一个落单数字。这个解法特别漂亮因为它把“找两个落单数字”的问题转化成“找两个能在某个二进制位上区分开的数字”然后用分组把问题拆成两个已解决的问题。整个流程里用到了异或、lowbit、按位分组三个技巧一道题串起一堆知识点所以我个人非常推荐把这道题练熟。顺便说一句“按位分组”这个思路不只适用于这个场景在解决某些需要按条件拆分的状态压缩问题时也经常出现。关键是要先找到一个能把目标拆分出来的“区分位”然后利用位运算做分类。4.3 子集枚举一个for循环解决暴力搜索题目给定一个不含重复元素的数组nums返回所有可能的子集。回溯写法能解但现在我们用位运算写数组长度n子集总数是2^n每个子集对应一个mask从0到2^n-1循环根据mask每一位是否为1决定是否取nums[i]。vectorvectorint subsets(vectorint nums) { int n nums.size(); vectorvectorint res; for (int mask 0; mask (1 n); mask) { vectorint cur; for (int i 0; i n; i) { if (mask (1 i)) { cur.push_back(nums[i]); } } res.push_back(cur); } return res; }循环次数是O(2^n)每个mask再遍历一遍n个元素所以总复杂度是O(n * 2^n)。当n小于等于15到20左右这个暴力枚举完全可行。很多人刚开始学算法时总觉得暴力枚举是贬义词但在位运算辅助下这种“机械式暴力”其实清晰又不易出错反而是很多题目最优解的基础。比如“目标和为某值的所有子集”“所有长度为k的组合”都完全可以用mask枚举后再判断条件。子集枚举还有一个超实用的变种枚举某个集合的真子集。如果你已经有一个mask表示集合要枚举它的所有子集写法是很经典的for (int sub mask; sub; sub (sub - 1) mask)。这行代码能在一个循环内不重不漏地枚举出mask的所有非空子集在状压DP里属于必须会写的高频套路。理解它其实也不难sub - 1会改变最低位的1再跟mask做与运算就保证一直在mask的范围内更新。4.4 状态压缩DP用整数状态代替多维数组状态压缩DP是位运算进阶应用里最值钱的地方。拿一个经典问题举例给定一个带权有向图求经过所有顶点恰好一次的最短路径旅行商问题的朴素版本。如果用dfs 回溯硬搜状态是“当前在哪个点”加上“哪些点已经走过”这个状态用普通变量很难精确描述。位运算给了个很好的表达方式用一个整数mask表示“哪些点已经走过”第i位为1表示走过点i。那么状态可以写成dp[mask][v]表示“已经走过的点集合是mask并且当前停在点v时的最短路径”。初始状态是dp[1 start][start] 0表示只走了起点。转移时枚举下一个可以走的点u只要mask (1 u)为0就表示u还没去过可以尝试更新dp[mask | (1 u)][u]。这类DP之所以好用一是因为mask直接作为数组下标空间和时间都容易预估二是因为“检查某个点是否走过”和“标记某个点被走过”这两件事恰好对应位运算里的“判断位为1”和“把某位置1”代码逻辑非常顺。很多看起来要开多维布尔数组的问题用mask压缩后可以直接堆进一个一维或二维DP表里这也是为什么状态压缩DP和位运算几乎绑定在一起。如果你对N皇后这类搜索题有印象会发现它们也能用位运算优化。经典做法是用三个整数分别记录“列冲突、主对角线冲突、副对角线冲突”每一行递归时用一个整数表示“当前行哪些列可以放皇后”通过位运算快速找可用位置比用布尔数组递归判断要快一个量级。这种优化在解数独、N皇后数量很大时依然能扛住属于高级选手的常用武器。4.5 快速幂和乘法的位实现一线天级的底层优化快速幂在前面技巧部分讲过思路这里给出一个可以直接抄的模板long long quickPow(long long a, long long b, long long mod) { long long res 1; while (b 0) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }你看if (b 1)判断当前指数最低位是否为1b 1把指数逐位处理掉。一个循环遍历指数的所有二进制位一轮是O(log b)。这个模板在密码学、概率论里求大数幂模时用得非常基础算法面试中也会频繁出现比如求“一个大组合数取模”的时候前置步骤几乎都长这样。再补一个用移位实现加法和乘法的思路加法a b可以拆成(a ^ b) ((a b) 1)。其中(a ^ b)是每位的和不带进位(a b) 1是进位结果把这两部分再递归求和直到进位为0为止。虽然实际工程里写a b就够了但如果你想深究CPU里加法器怎么算这个递归式就是本质。面试时偶尔有人问“不用加号实现加法”答案就是从异或和与两个操作入手。5. 常见问题与排查技巧位运算踩坑实录再聪明的技巧落到具体语言和编译器里都可能有不愉快的意外。这里我按踩坑频率从高到低整理一份清单每一条都是真实犯过错才记住的。5.1 运算符优先级x 1 0到底判断了什么这条坑几乎每个从C系语言入门的人都踩过。问题出在的优先级高于所以x 1 0会被解析成x (1 0)也就是x 0结果恒为0逻辑上完全不是你以为的“判断x的二进制最低位是否为0”。正确的写法应该是(x 1) 0或者更直白地用!(x 1)。不仅仅是在与操作符这里|、^的优先级也都比低所以凡是“位运算结果参与比较”的表达式我都会先把位运算那一整块用括号包起来。这不是优柔寡断是实实在在能救命。运算符优先级相关的还有一处x (1 i)在判断某一位是否为1时非常容易跟!或连用出现优先级问题。举个例子if (x (1 i) ! 0)会直接编译报错或者结果错乱因为!先算。统一写成if ((x (1 i)) ! 0)就好。5.2 右移到底是算术右移还是逻辑右移C/C里对于有符号整数右移运算实现是由编译器决定的但绝大多数编译器在主流的平台上都做算术右移也就是负数右移左边补1正数右移左边补0无符号整数右移则是逻辑右移始终补0。Java里则把这两种区分得更细是有符号右移负数补1是无符号右移左边始终补0。这个区别对你写代码的影响很大。如果你用x 1来对负数做“除以2”得到的是向下取整的结果和数学上的除法不完全等价。比如-3右移1位算术右移结果是-2而不是-1.5向下取整的 -2这里恰好一致但如果换成-1右移1位得到的是-1还是0就取决于移位方式。所以涉及负数时我一般避免用右移代替除法除非你明确知道自己在做位运算场景的向下整数除法。5.3 取反负数到底算出来是什么前面讲过~5是-6、~0是-1。如果你没彻底理解补码看到这个结果会以为计算机出错了。实际上是因为所有位都翻转在补码解释下~x总是等于-x-1。这个“-x-1”规律可以帮你心算出任何取反结果~100就是-101~(-7)就是6。务必把这个映射练熟否则调试时见到~mask这种表达式就会一头雾水。另外一个隐蔽的问题是在C/C中~x的结果类型可能因为整数提升变得和你想的不一样。比如对char类型变量取反会先提升成int再取反如果你原本以为只翻转了8位实际翻转了32位后续跟char掩码比较时就会莫名其妙。处理这类问题时建议在取反后立刻跟一个掩码做 运算比如(~x) 0xFF确保只留下你关心的那几位。5.4 移位数超过类型宽度是未定义行为C/C标准里如果移动的位数大于等于类型的位宽结果是未定义行为。比如int x 1; x 33;在32位int上这行代码在不同编译器上可能给出完全不一致的结果有些会当0处理有些会做移位位数的模运算甚至编译器优化会把它改得面目全非。写位运算代码前最好判断位移量是不是合法的。如果你的代码依赖“按n位取模”来让位移总数超过位宽那一定要改成显式取模或者干脆用循环。这个坑在做快速幂和状态压缩DP时尤其容易犯。比如1 i里如果i越来越大超过31就出问题。解决方法是确认数据范围或者使用64位的1LL i。最好在写代码前先估算mask最多有多少位会不会超过当前类型的位宽。5.5 有符号数左移溢出对有符号整数做左移如果移动后结果超出了该类型能表示的范围这是未定义行为。例如int x 0x7fffffff; x 1;结果是正数的两倍直接溢出成负数具体变成什么完全看实现。所以当你用1 i构造掩码、而i很大的时候建议用1u i也就是无符号版本。如果是64位状态压缩就用1ULL i。这样做既避免了未定义行为的风险也保证后续位运算不会出现奇怪的负号问题。5.6 别为了用位运算而用位运算位运算非常快但你写出的代码最终还是要人读的。我在工程代码里见过有人把普通的加法写成一连串移位和异或非得让后来人研究半天才看懂这属于炫技过头。合理的做法是性能热点里用位运算优化业务逻辑里能写清晰就写清晰。比如判断奇偶确实是x 1但如果你只是为了判断一个变量是否偶数写x % 2 0完全没有性能问题编译器也会把取模优化成按位与。真正需要手写位运算优化的通常是循环次数在百万亿级别、并且确实能减少内存开销的场景比如状态压缩DP、位图索引、底层协议解析。其余时候可读性优先。5.7 常见易错点速查表场景易错点正确写法判断某一位是否为1x (1 i) 1结果永远为0(x (1 i)) ! 0清零某一位用或运算x ~(1 i)置位某一位用与运算x翻转某一位忘了异或x ^ (1 i)取2的幂忘记判断正数x 0 (x (x-1)) 0右移代替除法负数行为不一致谨慎使用明确语义构造全1掩码写死0xffffffff(1 n) - 1动态生成大位宽数据用int存64位状态用uint64_t或long long取反后位数不对忽略整数提升(~x) 0xFF截断位移量越界编译器行为依赖先判断n是否合法这个表里的内容几乎都是我复盘调试记录时总结出来的。每次出现诡异结果第一步先检查运算符优先级第二步检查类型位宽第三步检查符号位。三步走完大部分位运算的坑都能定位到。写在最后回头再看位运算你会发现它本质上是在利用二进制这个底层表达方式把很多看似复杂的逻辑化简成几个机器指令。不管是判断奇偶、子集枚举、状态压缩DP还是树状数组里的lowbit它们的共同点都是“把一个整数当成一组开关来用”。我自己的体会是一开始练位运算时会有些不适应因为十进制思维太根深蒂固了但当你在几道题目里尝到“几行代码省掉一个DP数组”的甜头之后就会慢慢习惯这种思考方式。最后分享一个小习惯我每次刷题遇到能用位运算的场景都会先在草稿纸上把涉及的几个数写成二进制竖式手动算一遍位运算结果再对着代码检查。这个过程看似慢但能帮你建立起对每一位的敏感度。之后遇到更复杂的mask操作时你就不用再拿纸笔了脑子里直接能“看”到位的变换。这个练法推荐给你希望能在你啃位运算的时候省点时间。